# DenseZDD: A Compact and Fast Index for Families of Sets +
## 8 Experimental Results
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Data Set** & \(n\) & \(|F|\) & \(\|F\|\) & **\#roots** & **\#nodes** \\ \hline rect1x10000 & 10,000 & 10,000 & 10,000 & 1 & 10,001 \\ rect5x2000 & 10,000 & \(3.2\times 10^{16}\) & \(1.6\times 10^{17}\) & 1 & 10,001 \\ rect100x100 & 10,000 & \(1.0\times 10^{200}\) & \(1.0\times 10^{202}\) & 1 & 10,001 \\ rect2000x5 & 10,000 & \(8.7\times 10^{1397}\) & \(1.7\times 10^{1401}\) & 1 & 10,001 \\ rect10000x1 & 10,000 & \(1\) & 10,000 & 1 & 10,001 \\ randomjoin256 & 32,740 & \(4.3\times 10^{9}\) & \(1.7\times 10^{10}\) & 1 & 25,743 \\ randomjoin2048 & 32,765 & \(1.7\times 10^{13}\) & \(7.0\times 10^{13}\) & 1 & 375,959 \\ randomjoin8192 & 32,768 & \(3.6\times 10^{15}\) & \(1.4\times 10^{16}\) & 1 & \(1.3\times 10^{6}\) \\ randomjoin16384 & 32,768 & \(2.8\times 10^{16}\) & \(1.1\times 10^{17}\) & 1 & \(1.9\times 10^{6}\) \\ bddqueen13 & 169 & 73,712 & 958,256 & 1 & 204,782 \\ bddqueen14 & 196 & 365,596 & \(5.1\times 10^{6}\) & 1 & 911,421 \\ bddqueen15 & 225 & \(2.3\times 10^{6}\) & \(3.4\times 10^{7}\) & 1 & \(4.8\times 10^{6}\) \\ T40I10D100K:0.001 & 925 & \(7.0\times 10^{7}\) & \(8.2\times 10^{8}\) & 1 & \(1.1\times 10^{6}\) \\ T40I10D100K:0.0005 & 933 & \(2.0\times 10^{8}\) & \(2.1\times 10^{9}\) & 1 & \(6.5\times 10^{6}\) \\ T40I10D100K:0.0001 & 942 & \(1.2\times 10^{10}\) & \(1.5\times 10^{11}\) & 1 & \(1.9\times 10^{8}\) \\ accidents:0.1 & 76 & \(1.1\times 10^{7}\) & \(1.1\times 10^{8}\) & 1 & 36,324 \\ accidents:0.05 & 106 & \(8.3\times 10^{7}\) & \(9.3\times 10^{8}\) & 1 & 183,144 \\ accidents:0.01 & 167 & \(4.1\times 10^{9}\) & \(5.3\times 10^{10}\) & 1 & \(4.7\times 10^{6}\) \\ chess:0.1 & 62 & \(4.6\times 10^{9}\) & \(6.4\times 10^{10}\) & 1 & \(1.1\times 10^{6}\) \\ chess:0.05 & 67 & \(4.1\times 10^{10}\) & \(6.2\times 10^{11}\) & 1 & \(3.1\times 10^{6}\) \\ chess:0.01 & 72 & \(1.6\times 10^{12}\) & \(2.9\times 10^{13}\) & 1 & \(5.8\times 10^{6}\) \\ connect:0.05 & 87 & \(4.1\times 10^{11}\) & \(6.9\times 10^{12}\) & 1 & 331,829 \\ connect:0.01 & 110 & \(1.7\times 10^{13}\) & \(3.2\times 10^{14}\) & 1 & \(2.3\times 10^{6}\) \\ connect:0.005 & 116 & \(6.8\times 10^{13}\) & \(1.3\times 10^{15}\) & 1 & \(4.1\times 10^{6}\) \\
16-adder\_col & 66 & \(9.7\times 10^{6}\) & \(2.7\times 10^{8}\) & 17 & \(1.5\times 10^{6}\) \\ C1908 & 66 & \(3.7\times 10^{8}\) & \(1.1\times 10^{10}\) & 25 & 133,379 \\ C3540 & 100 & \(5.0\times 10^{6}\) & \(1.3\times 10^{8}\) & 22 & \(1.5\times 10^{6}\) \\ C499 & 82 & \(4.9\times 10^{11}\) & \(1.9\times 10^{13}\) & 32 & 140,932 \\ C880 & 120 & \(2.4\times 10^{6}\) & \(7.0\times 10^{7}\) & 26 & 606,310 \\ comp & 64 & 196,606 & \(6.0\times 10^{6}\) & 3 & 589,783 \\ my\_adder & 66 & 655,287 & \(2.0\times 10^{7}\) & 17 & 884,662 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Detail of data sets and their ZDD size. In Table 4, we show the conversion time from the ZDD to the DenseZDD and the _getnode_ time on each structure for each data set. Conversion time is composed of three parts: converting a given ZDD to raw parentheses, bits, and integers, constructing the succinct representation of them, and compressing the BP of the zero-edge tree. The conversion time is almost linear in the input size. This result shows its scalability for large data. For each data set except for rectrx\(w\), the _getnode_ time on the DenseZDD is almost two times larger than that on the ZDD and that on the dummy-compressed DenseZDD is five to twenty times larger than that on the ZDD.