# Storing Set Families More Compactly with Top ZDDs
## 5 Experimental Comparison
\begin{table}
\begin{tabular}{c c c c c} \hline \hline  & **Top ZDD** & **DenseZDD** &
\begin{tabular}{c} **Theoretical Size of ZDD** \\ \(\left(2n\lfloor\log n\rfloor+n\lfloor\log c\rfloor\right)\)/8 \\ \end{tabular} \\ \hline \(A=100,B=50\) & **3863** & 9544 & 9882 \\ \hline \(A=400,B=200\) & **13,654** & 146,550 & 206,025 \\ \hline \(A=1000,B=500\) & **43,191** & 966,519 & 1,440,375 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: For the set \(\left\{1,\ldots,A\right\}\) with \(A\) elements, the family of all the sets with cardinality at most \(B\). \begin{table}
\begin{tabular}{c c c c c c} \hline \hline  & **Top ZDD** & **DenseZDD** &
\begin{tabular}{c} **Theoretical Size of ZDD** \\ \(\left(2n\lfloor\log n\rfloor+n\lfloor\log c\rfloor\right)\)/8 \\ \end{tabular} \\ \hline \(A=100,B=50\) & **3863** & 9544 & 9882 \\ \hline \(A=400,B=200\) & **13,654** & 146,550 & 206,025 \\ \hline \(A=1000,B=500\) & **43,191** & 966,519 & 1,440,375 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Knapsack set families with random weights. \(A\) is the number of elements, \(W\) is the maximum weight of an element, \(C\) is the capacity of the knapsack. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline  & **Top ZDD** & **DenseZDD** &
\begin{tabular}{c} **Theoretical** \\ **Size of ZDD** \\ \end{tabular} & **t** & **p** \\ \hline \(A=100,W=1000\), & **1,630,136** & 1,736,228 & 2,453,695 & 49 & 0 \\ \hline \(A=200,W=100\), & **976,577** & 1,409,626 & 2,026,484 & 175 & 0 \\ \hline \(A=1000,W=100\), & **2,078,731** & 2,919,211 & 4,475,977 & 1124 & 0 \\ \hline \(A=5000,W=100\), & **1,138,778** & 1,731,654 & 2,869,185 & 1024 & 0 \\ \hline \(A=1000,W=10\), & **1,404,838** & 2,627,430 & 4,003,302 & 951 & 0 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Knapsack set families with random weights. \(A\) is the number of elements, \(W\) is the maximum weight of an element, \(C\) is the capacity of the knapsack. We found that for all data sets, the top ZDD uses less space than the theoretical size of the standard ZDD. We also confirmed that the data sets in Tables 2-4 can be compressed very well by top ZDDs. Table 5 shows the results on the sets of solutions of knapsack problems. Top ZDD uses less space than DenseZDD in all cases, and in some cases, the memory usage of top ZDD is almost half that of DenseZDD. Tables 6 and 7 show the results for families of matching in a graph and frequent itemsets, respectively. There are a few cases where the DenseZDD uses less space than the top ZDD. The results above are for monotone set families, that is, any subset of the set of the family also exists in the family. Tables 8 and 9 show results on non-monotone set families. For the set of edges on the path from the bottom left corner to the top right corner of an \(n\times n\) grid graph, the top ZDD uses less space than the DenseZDD, and for \(n=9\), the top ZDD uses about \(1/3\) the memory of DenseZDD. On the other hand, for the sets of all the solutions of the \(n\)-queen problem, the top ZDD uses about \(10\%\) more space than the DenseZDD. From these experiments, we confirmed that top ZDD uses less space than DenseZDD for many set families. Next, we show the construction time and edge traversal time of the top ZDD and the DenseZDD in Tables 10-17. For edge traversal time, we traversed from the root of a ZDD towards terminals by randomly choosing 0- or 1-edge 65,536 times, and took the average. When we arrived at a terminal, we restarted from the root. \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,B=50\) & 0.011 & 0.006 & 10.892 & 0.320 \\ \hline \(A=400,B=200\) & 0.269 & 0.123 & 16.019 & 0.534 \\ \hline \(A=1000,B=500\) & 2.013 & 0.878 & 20.101 & 0.412 \\ \hline \hline \end{tabular}
\end{table} 
Table 13: Knapsack set families with random weights.