# DenseZDD: A Compact and Fast Index for Families of Sets +
## 8 Experimental Results
The traversal times on dummy-compressed DenseZDDs are seven times slower and the search time on them are two times slower than DenseZDDs. \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \multirow{2}{*}{**Data Set**} & \multicolumn{3}{c}{**Conversion Time (s)**} & \multicolumn{3}{c}{**Getnode Time (s)**} \\ \cline{2-7}  & **convert** & **const.** & **comp.** & **Z** & **DZ** & **DZ\({}_{dc}\)** \\ \hline rect1x10000 & 0.007 & 0.009 & 0.008 & 0.001 & 0.001 & 0.005 \\ rect5x2000 & 0.006 & 0.015 & 0.011 & 0.000 & 0.001 & 0.006 \\ rect100x100 & 0.006 & 0.014 & 0.009 & 0.001 & 0.001 & 0.005 \\ rect2000x5 & 0.006 & 0.016 & 0.012 & 0.000 & 0.001 & 0.005 \\ rect10000x1 & 0.504 & 0.015 & 0.009 & 0.000 & 0.001 & 0.008 \\ randomjoin256 & 0.025 & 0.105 & 0.005 & 0.001 & 0.002 & 0.013 \\ randomjoin2048 & 0.254 & 0.263 & 0.001 & 0.036 & 0.037 & 0.189 \\ randomjoin8192 & 0.946 & 0.526 & 0.000 & 0.156 & 0.164 & 0.710 \\ randomjoin16384 & 1.463 & 0.692 & 0.010 & 0.235 & 0.278 & 1.123 \\ bddqueen13 & 0.175 & 0.087 & 0.003 & 0.009 & 0.017 & 0.159 \\ bddqueen14 & 0.926 & 0.415 & 0.019 & 0.059 & 0.074 & 0.692 \\ bddqueen15 & 6.217 & 2.438 & 0.142 & 0.426 & 0.402 & 3.498 \\ T40I10D100K:0.001 & 0.934 & 0.814 & 0.037 & 0.089 & 0.218 & 0.872 \\ T40I10D100K:0.0005 & 6.006 & 3.958 & 0.175 & 0.771 & 1.088 & 4.706 \\ T40I10D100K:0.0001 & 233.006 & 120.423 & 4.378 & 32.316 & 30.181 & 122.104 \\ accidents:0.1 & 0.026 & 0.040 & 0.023 & 0.002 & 0.005 & 0.033 \\ accidents:0.05 & 0.162 & 0.094 & 0.022 & 0.012 & 0.023 & 0.161 \\ accidents:0.01 & 5.901 & 1.949 & 0.075 & 0.785 & 0.657 & 4.568 \\ chess:0.1 & 1.149 & 0.455 & 0.016 & 0.142 & 0.145 & 1.130 \\ chess:0.05 & 3.319 & 1.263 & 0.085 & 0.471 & 0.414 & 2.895 \\ chess:0.01 & 5.829 & 2.408 & 0.098 & 0.847 & 0.729 & 4.662 \\ connect:0.05 & 0.289 & 0.136 & 0.002 & 0.023 & 0.037 & 0.227 \\ connect:0.01 & 2.287 & 0.945 & 0.033 & 0.297 & 0.268 & 1.625 \\ connect:0.005 & 4.377 & 1.716 & 0.080 & 0.579 & 0.491 & 2.996 \\
16-adder\_col & 1.318 & 0.585 & 0.010 & 0.119 & 0.137 & 1.821 \\ C1908 & 0.085 & 0.070 & 0.016 & 0.006 & 0.011 & 0.147 \\ C3540 & 1.319 & 0.563 & 0.017 & 0.098 & 0.119 & 1.488 \\ C499 & 0.084 & 0.073 & 0.010 & 0.007 & 0.010 & 0.140 \\ C880 & 0.491 & 0.249 & 0.005 & 0.034 & 0.048 & 0.551 \\ comp & 0.445 & 0.232 & 0.002 & 0.032 & 0.046 & 0.683 \\ my\_adder & 0.743 & 0.375 & 0.009 & 0.061 & 0.083 & 0.930 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Converting time and _getnode_ time. In Table 6, we show the counting time and the random sampling time. For each data set, the counting time on the DenseZDD and the random sampling time of the naive algorithm on both the DenseZDD and the dummy-compressed DenseZDD are not so far from those on the ZDD, while the counting time on the dummy-compressed DenseZDD is two to ten times larger than the ZDD. For each data set, the random sampling time of the binary search-based algorithm is two to hundred times smaller than the ZDD. For Boolean functions, the algorithm is three to six times slower. There is not much difference between DenseZDDs and dummy-compressed DenseZDDs. From the above results, we conclude that DenseZDDs are more compact than ordinary ZDDs unless the dummy node ratio is extremely high, and the membership operations for DenseZDDs are much faster if \(n\) is large or the number of 0-edges from terminal nodes to each node is large. We observed that DenseZDD makes traversal time approximately triple, search time approximately one-tenth, and random sampling time approximately one-third compared to the original ZDDs.