# Storing Set Families More Compactly with Top ZDDs
## 5 Experimental Comparison  
We compare our top ZDD with existing data structures. We implemented top ZDD with C++ and measured the required space for storing the data structure. For comparison, we used the following three data structures. * top ZDD (proposed): we measured the space for storing the data structures in Table 1.
* DenseZDD [11]: data structures for representing ZDDs using succinct data structures. Two data structures are proposed; one support constant time queries and the other has \(\mathrm{O}(\log n)\) time complexity. We used the latter that uses less space. * a standard ZDD: a data structure which naively represents ZDDs. We store for each node its label and two pointers corresponding to a 0-edge and a 1-edge. Space is \(2n\lfloor\log n\rfloor+n\lfloor\log c\rfloor\) bits where \(n\) is the number of nodes of a ZDD and \(c\) is the size of the universe of a set family. We constructed ZDDs of the following set families. * The power set of a set \(\{1,\ldots,A\}\) with \(A\) elements. * For the set \(\{1,\ldots,A\}\) with \(A\) elements, the family of all the set \(S\) satisfying \((\)The maximum value of \(S)-(\)The minimum value of \(S)\leq B\). * For the set \(\{1,\ldots,A\}\) with \(A\) elements, the family of all the sets with cardinality at most \(B\). * Knapsack set families with random weights. That is, for \(i\)-th element in a set (\(1\leq i\leq A\)), we define its weight \(w_{i}\) as a uniformly random integer in \([1,W]\), then sort the elements in decreasing order of weights, and construct a set family consisting of all sets with weight at most \(C\). Because of the randomness of the input, we ran the experiment 1024 times for each setting and calculate the t-value and \(p\)-value between top ZDD and DenseZDD. * The family of edge sets which are a matching of a given graph. As for graphs, we used the \(8\times 8\) grid graph, the complete graph with 12 vertices \(K_{12}\), and a real communication network _\"Interroute\"_. * Set families of frequent itemsets. * Families of edge sets which are paths from the bottom left vertex to the top-right vertex in \(n\times n\) grid graph, for \(n=6,7,8,9\). * Families of solutions of the \(n\)-queen problem (The \(n\)-queen problem is to find an arrangement of \(n\) queens on the \(n\times n\) chessboard such that no two queens threaten each other. Here, all possible arrangements are stored in a ZDD), for \(n=11,12,13\). We used several values for the parameters \(A,B,C,W\). The results are shown in Tables 2-9. The unit of size is a byte. \begin{table}
\begin{tabular}{c c c c} \hline \hline  & **Top ZDD** & **DenseZDD** &
\begin{tabular}{c} **Theoretical Size of ZDD** \\ \((2n\lfloor\log n\rfloor+n\lfloor\log c\rfloor)/8\) \\ \end{tabular} \\ \hline \(A=1000\) & **2297** & 4185 & 3750 \\ \hline \(A=50\),000 & **2507** & 178,764 & 300,000 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: The power set of \(\{1,\ldots,A\}\). \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 \(8\times 8\) grid & **12,246** & 16,150 & 18,014 \\ \hline complete graph \(K_{12}\) & 23,078 & **16,304** & 25,340 \\ \hline _“Interoute”_ & **30,844** & 39,831 & 50,144 \\ \hline \hline \end{tabular}
\end{table} 
Table 6: The family of edge sets which are matching of a given graph. \begin{table}
\begin{tabular}{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=500,B=250\) & **2471** & 227,798 & 321,594 \\ \hline \(A=1000,B=500\) & **2551** & 321,594 & 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\).