# DenseZDD: A Compact and Fast Index for Families of Sets +
## 8 Experimental Results  
We ran experiments to evaluate the compression, construction, and operation times of DenseZDDs. We implemented the algorithms described in Sections 3 and 3.2 in C/C++ languages on top of the SAPPORO BDD package, which is available at [[https://github.com/takemaru/graphillion/tree/master/src/SAPPOROBDD](https://github.com/takemaru/graphillion/tree/master/src/SAPPOROBDD)]([https://github.com/takemaru/graphillion/tree/master/src/SAPPOROBDD](https://github.com/takemaru/graphillion/tree/master/src/SAPPOROBDD)) and can be found as an internal library of Graphillion [18]. The package uses 32 bytes per ZDD node. The breakdown of 32 bytes of a ZDD node is as follows: 5 bytes as a pointer for the 1-child, 5 bytes as a pointer for the 0-child, 2 bytes as an index. In addition, we use a closed hash table to execute _getnode_ operation. The size of the hash table of SAPPOROBDD is \(5\times 2\times n\) bytes, and 5 bytes per each node to chain ZDD nodes that have the same key computed from its attribute-triple. Since DenseZDD does not require such hash table to execute _getnode_, we consider that the space used by the hash table should be included in the memory consumption of ZDD nodes. The experiments are performed on a machine with 3.70 GHz Intel Core i7-8700K and 64 GB memory running Windows Subsystem for Linux (Ubuntu) on Windows 10. We show the characteristics of the data sets in Table 2. As artificial data sets, we use rect_rxw_, which represents families of sets \(\bigsqcup_{i=0}^{r-1}\{\{iw+1\},\ldots,\{iw+w\}\}\). Data set randomjoin_k_ is a ZDD that represents the join \(C_{1}\sqcup\cdots\sqcup C_{4}\) of four ZDDs for random families \(C_{1},\ldots,C_{4}\) consisting of \(k\) sets of size one drawn from the set of \(n=32768\) items. Data set bddquen_k_ is a ZDD that stores all solutions for \(k\)-queen problem. As real data sets, data set _filename:p_ is a ZDD that is constructed from itemset data ([[http://fimi.ua.ac.be](http://fimi.ua.ac.be)]([http://fimi.ua.ac.be](http://fimi.ua.ac.be))) by using the algorithm of all frequent itemset mining, named LCM over ZDD [3], with minimum support \(p\). The other ZDDs are constructed from Boolean functions data ([[https://dddd.fit.cvut.cz/prj/Benchmarks/](https://dddd.fit.cvut.cz/prj/Benchmarks/)]([https://dddd.fit.cvut.cz/prj/Benchmarks/](https://dddd.fit.cvut.cz/prj/Benchmarks/))). These data are commonly used to evaluate the size of ZDD-based data structures [2; 19; 20]. These ZDDs represent Boolean functions in a conjunctive normal form as families of sets of literals. For example, a function \(x_{1}\overline{x_{2}}+\overline{x_{2}}x_{3}+x_{3}x_{1}\) is translated into the family of sets \(\{\{x_{1},\overline{x_{2}}\},\{\overline{x_{2}},x_{3}\},\{x_{3},x_{1}\}\}\). In Table 3, we show the sizes of the original ZDDs, the DenseZDDs, the dummy-compressed DenseZDDs and their compression ratios. The _dummy node ratio,_ denoted by \(\delta\), of a DenseZDD is the ratio of the number of dummy nodes to that of both real nodes and dummy nodes in the DenseZDD. We compressed FID for the dummy node vector if the dummy node ratio is more than 75%. We observe that DenseZDDs are five to eight times smaller than original ZDDs, and dummy-compressed DenseZDDs are six to ten times smaller than original ZDDs. We also observe that dummy node ratios highly depend on data. They ranged from about 5% to 30%. For each data set, the higher the dummy node ratio was, the lower the compression ratio of the size of the DenseZDD to that of the ZDD became, and the higher the compression ratio of the size of the dummy-compressed DenseZDD to that of the DenseZDD became.