# DenseZDD: A Compact and Fast Index for Families of Sets +
## 8 Experimental Results
\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \multirow{2}{*}{**Data Set**} & \multicolumn{3}{c}{**Size (byte)**} & \multicolumn{3}{c}{**Comp. Ratio**} & \multirow{2}{*}{\(\delta\)} \\ \cline{2-2} \cline{5-6}  & **Z** & **DZ** & **DZ\({}_{dc}\)** & **DZ** & **DZ\({}_{dc}\)** \\ \hline rect1x10000 & 320,032 & 14,662 & 10,372 & 0.000 & 0.046 & 0.032 \\ rect5x2000 & 320,032 & 36,947 & 29,227 & 0.444 & 0.115 & 0.091 \\ rect100x100 & 320,032 & 38,014 & 29,648 & 0.498 & 0.119 & 0.093 \\ rect2000x5 & 320,032 & 38,078 & 32,100 & 0.500 & 0.119 & 0.100 \\ rect10000x1 & 320,032 & 38,078 & 34,048 & 0.500 & 0.119 & 0.106 \\ randomjoin256 & 823,760 & 792,703 & 279,719 & 0.978 & 0.962 & 0.340 \\ randomjoin2048 & \(1.2\times 10^{7}\) & \(2.5\times 10^{6}\) & \(1.6\times 10^{6}\) & 0.821 & 0.210 & 0.135 \\ randomjoin8192 & \(4.0\times 10^{7}\) & \(5.6\times 10^{6}\) & \(4.7\times 10^{6}\) & 0.424 & 0.139 & 0.115 \\ randomjoin16384 & \(6.0\times 10^{7}\) & \(7.7\times 10^{6}\) & \(6.8\times 10^{6}\) & 0.145 & 0.128 & 0.113 \\ bddqueen13 & \(6.1\times 10^{6}\) & 846,809 & 752,775 & 0.466 & 0.138 & 0.123 \\ bddqueen14 & \(2.7\times 10^{7}\) & \(4.2\times 10^{6}\) & \(3.7\times 10^{6}\) & 0.510 & 0.153 & 0.136 \\ bddqueen15 & \(1.4\times 10^{8}\) & \(2.5\times 10^{7}\) & \(2.2\times 10^{7}\) & 0.558 & 0.171 & 0.151 \\ T40I10D100K:0.001 & \(3.6\times 10^{7}\) & \(8.0\times 10^{6}\) & \(5.3\times 10^{6}\) & 0.826 & 0.220 & 0.148 \\ T40I10D100K:0.0005 & \(2.1\times 10^{8}\) & \(4.0\times 10^{7}\) & \(3.0\times 10^{7}\) & 0.748 & 0.191 & 0.141 \\ T40I10D100K:0.0001 & \(6.0\times 10^{9}\) & \(1.2\times 10^{9}\) & \(9.4\times 10^{8}\) & 0.703 & 0.200 & 0.159 \\ accidents:0.1 & \(1.2\times 10^{6}\) & 125,440 & 117,714 & 0.083 & 0.108 & 0.101 \\ accidents:0.05 & \(5.9\times 10^{6}\) & 672,553 & 634,169 & 0.079 & 0.115 & 0.108 \\ accidents:0.01 & \(1.5\times 10^{8}\) & \(2.0\times 10^{7}\) & \(1.9\times 10^{7}\) & 0.089 & 0.135 & 0.128 \\ chess:0.1 & \(3.7\times 10^{7}\) & \(4.6\times 10^{6}\) & \(4.4\times 10^{6}\) & 0.098 & 0.127 & 0.120 \\ chess:0.05 & \(1.0\times 10^{8}\) & \(1.3\times 10^{7}\) & \(1.2\times 10^{7}\) & 0.098 & 0.131 & 0.124 \\ chess:0.01 & \(1.8\times 10^{8}\) & \(2.5\times 10^{7}\) & \(2.3\times 10^{7}\) & 0.118 & 0.135 & 0.127 \\ connect:0.05 & \(1.1\times 10^{7}\) & \(1.3\times 10^{6}\) & \(1.2\times 10^{6}\) & 0.206 & 0.122 & 0.112 \\ connect:0.01 & \(7.3\times 10^{7}\) & \(9.7\times 10^{6}\) & \(9.0\times 10^{6}\) & 0.204 & 0.133 & 0.124 \\ connect:0.005 & \(1.3\times 10^{8}\) & \(1.8\times 10^{7}\) & \(1.6\times 10^{7}\) & 0.202 & 0.133 & 0.124 \\
16-adder\_col & \(4.9\times 10^{7}\) & \(6.2\times 10^{6}\) & \(5.9\times 10^{6}\) & 0.124 & 0.127 & 0.122 \\ C1908 & \(4.3\times 10^{6}\) & 487,434 & 470,422 & 0.027 & 0.114 & 0.110 \\ C3540 & \(4.6\times 10^{7}\) & \(5.9\times 10^{6}\) & \(5.6\times 10^{6}\) & 0.152 & 0.128 & 0.122 \\ C499 & \(4.5\times 10^{6}\) & 513,322 & 499,158 & 0.009 & 0.114 & 0.111 \\ C880 & \(1.9\times 10^{7}\) & \(2.5\times 10^{6}\) & \(2.3\times 10^{6}\) & 0.305 & 0.129 & 0.120 \\ comp & \(1.9\times 10^{7}\) & \(2.4\times 10^{6}\) & \(2.2\times 10^{6}\) & 0.234 & 0.127 & 0.119 \\ my\_adder & \(2.8\times 10^{7}\) & \(3.8\times 10^{6}\) & \(3.5\times 10^{6}\) & 0.399 & 0.133 & 0.122 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Comparison of performance, where \(\delta\) denotes the dummy node ratio. \(Z\), \(DZ\), and \(DZ_{dc}\) indicate ordinary ZDDs, DenseZDDs and dummy-compressed DenseZDDs, respectively. In Table 5, we show the traversal time and the search time. The traverse operation uses \(zero(i)\) and \(one(i)\), while the membership operation uses \(topset(i,c)\) and \(one(i)\). We observe that the DenseZDD requires about three or four times longer traversal time and about 3-1500 times shorter search time than the original ZDD for each data set except for Boolean functions. These results show the efficiency of our algorithm of the \(topset(i,c)\) operation on DenseZDD using level ancestor operations.