Engineering Hybrid DenseZDDs

ZDDs Zero-suppressed Binary Decision Diagrams [Minato 93] have been proposed to store set families compactly. Though more compact than other representations, they still use large amount of memory to support dynamic operations such as taking union and intersection of set families. DenseZDDs and Hybrid DenseZDDs [Denzumi et al. 2014] have been proposed to compress the size of static and dynamic ZDDs, respectively. There exist however no implementations of Hybrid DenseZDDs and their practical performance is unknown. This paper engineers a practical implementation of Hybrid DenseZDDs. Because of our new compression algorithm, our new Hybrid DenseZDDs run in reasonable time using little working memory. Experimental results on the frequent itemset mining problem show that our algorithm uses 33i¾ź% of memory compared with a standard ZDD at the cost of 40i¾ź% increase in running time.