# Storing Set Families More Compactly with Top ZDDs
## 5 Experimental Comparison
\(A\) is the number of elements, \(W\) is the maximum weight of an element, \(C\) is the capacity of the knapsack. In this experiment, the t-values ranged from 630 to 915 for all settings, and the \(p\)-values were 0. \begin{table}
\begin{tabular}{c c c c c} \hline \hline  & \multicolumn{2}{c}{**Construction Time (s)**} & \multicolumn{2}{c}{**Traversal Time (\(\mu\)s)**} \\ \cline{2-5}  & **Top ZDD** & **DenseZDD** & **Top ZDD** & **DenseZDD** \\ \hline \(A=100,W=1000,C=10,000\) & 2.974 & 1.210 & 16.716 & 0.259 \\ \hline \(A=200,W=100,C=5000\) & 2.033 & 1.019 & 23.215 & 0.290 \\ \hline \(A=1000,W=100,C=1000\) & 7.010 & 1.481 & 21.698 & 0.534 \\ \hline \(A=5000,W=100,C=200\) & 2.084 & 0.954 & 7.365 & 0.519 \\ \hline \(A=1000,W=10,C=1000\) & 2.597 & 1.712 & 14.127 & 0.244 \\ \hline \hline \end{tabular}
\end{table} 
Table 14: The family of edge sets which are matching of a given graph. \begin{table}
\begin{tabular}{c c c c c} \hline \hline  & \multicolumn{2}{c}{**Construction Time (s)**} & \multicolumn{2}{c}{**Traversal Time (\(\mu\)s)**} \\ \cline{2-5}  & **Top ZDD** & **DenseZDD** & **Top ZDD** & **DenseZDD** \\ \hline \(A=100,W=1000,C=10,000\) & 2.974 & 1.210 & 16.716 & 0.259 \\ \hline \(A=200,W=100,C=5000\) & 2.033 & 1.019 & 23.215 & 0.290 \\ \hline \(A=1000,W=100,C=1000\) & 7.010 & 1.481 & 21.698 & 0.534 \\ \hline \(A=5000,W=100,C=200\) & 2.084 & 0.954 & 7.365 & 0.519 \\ \hline \(A=1000,W=10,C=1000\) & 2.597 & 1.712 & 14.127 & 0.244 \\ \hline \hline \end{tabular}
\end{table} 
Table 13: The family of edge sets which are matching of a given graph. \begin{table}
\begin{tabular}{c c c c c} \hline \hline  & \multicolumn{2}{c}{**Construction Time (s)**} & \multicolumn{2}{c}{**Traversal Time (\(\mu\)s)**} \\ \cline{2-5}  & **Top ZDD** & **DenseZDD** & **Top ZDD** & **DenseZDD** \\ \hline \({}^{*}\)_mushroom\({}^{*}\)_ & 0.093 & 0.037 & 14.100 & 0.198 \\ \hline \({}^{*}\)_retail\({}^{*}\)_ & 0.099 & 0.134 & 12.857 & 0.702 \\ \hline \({}^{*}\)_T40110D100K\({}^{*}\)_ & 0.198 & 0.117 & 13.788 & 0.183 \\ \hline \hline \end{tabular}
\end{table} 
Table 15: Set families of frequent item sets. In almost all cases, the Top ZDD construction took 1.5 to 2.5 times longer than the DenseZDD construction. The first data in Table 11 and the third data in Table 13 took particularly a long time, suggesting that DenseZDD is faster for families of sets where the size of the included sets is small compared to the total number of variables. The same reason is expected for the overall slowness of Top ZDD for n-queen problems. The second data of Table 15 is the only case that Top ZDD is constructed faster than DenseZDD. This is probably because this data is hardly compressed and DenseZDD is worse than the theoretical size of ordinary ZDD. In terms of traversal time, Top ZDD is 10 to 80 times slower than DenseZDD, which is a natural result since traversal time in DenseZDD is \(\mathrm{O}(\log n)\) time, while in Top ZDD it is \(\mathrm{O}(\log^{2}n)\) time. In addition, Top ZDD uses more succinct data structures for computation than DenseZDD, so it takes a larger constant coefficient. Basically, in DenseZDD, the traversal time increases with the number of nodes in the input ZDD, but this is not the case in Top ZDD. For example, there is a large variation in the ratio of the traversal speed of Top ZDD to that of DenseZDD in Tables 13-15. The reason for this is that when we execute traverse, Top ZDD performs recursive operations with a maximum \(\mathrm{O}(\log n)\) depth \(\mathrm{O}(\log n)\) times, but the actual number of times it is called depends on each entity.