# Storing Set Families More Compactly with Top ZDDs
## 4 Top ZDD
### Size of Top ZDDs  
The size of top ZDDs heavily depends on not only the number of vertices in the spanning tree after top DAG compression but also the number of complement edges for which we store some information. As a result, the size of top ZDDs becomes small if the number of nodes is reduced by top DAG compression and many common complement edges are shared.  
In the best case, top ZDDs are exponentially smaller than ZDDs.  
**Theorem 5**: _There exists a ZDD with \(n\) nodes to which the corresponding top ZDD has \(\mathrm{O}(\log n)\) vertices._  
Proof.: A ZDD storing a power set with \(n=2^{m}\) elements satisfies the claim. Figure 10 shows this ZDD and top ZDD. A ZDD representing a power set have a linear chain-like shape because no matter how we traverse 0-edges or 1-edges, we will always end up at the \(\top\) terminal. The spanning tree of the ZDD is a path consisting of \(2^{m}\) many 0-edges. Its top tree has a leaf corresponding to a 0-edge of length 1, and internal vertices form a complete binary tree with height \(m\). If we apply DAG compression to this top tree, we obtain the DAG of length \(m\) as shown in Figure 10. Sharing complement edges also works very well. The \(k\)-th vertex below representing vertical merge stores a 1-edge connecting a node with local preorder id \(2^{k-1}+1\) inside a cluster and a node with local preorder id \(2^{k-1}+2\). The  
\begin{table}
\begin{tabular}{c p{284.5 pt}} \hline \(bp\) & BP sequence representing the structure of \(T^{\prime}\) \\ \hline \(B_{dummy}\) & bit vector showing \(i\)-th leaf is a dummy vertex or not \\ \hline \(clsize\) & array storing cumulative sum of cluster sizes of the first to the \(i\)-th dummy leaves \\ \hline \(label\_span\) & array storing differences of labels of ending points of \(i\)-th non-dummy leaf \\ \hline \(type\_span\) & array showing the edge corresponding to the \(i\)-th non-dummy leaf is 0-edge or not \\ \hline \(B_{H}\) & bit vector showing \(i\)-th internal vertex is a vertical merge or not \\ \hline \(preorder\_diff\) & array storing differences of preorder ids between the top and the bottom boundary nodes of the vertex corresponding to \(i\)-th vertical merge \\ \hline \(label\_diff\) & array storing differences of labels between the top and the bottom boundary nodes of the vertex corresponding to \(i\)-th vertical merge \\ \hline \(B_{src\_root}\) & bit vector storing in unary codes the number of complement edges from each vertex \\ \hline \(dst\_root\) & array storing preorder ids of ending points of the \(i\)-th complement edge stored in root \\ \hline \(type\_root\) & array showing the \(i\)-th complement edge stored in the root is a 0-edge or not \\ \hline \(B_{edge}\) & bit vector storing in unary codes the number of complement edges from each vertex stored in the root \\ \hline \(src\_in\) & array storing local preorder ids of starting points of \(i\)-th complement edge stored in non-root \\ \hline \(dst\_in\) & array storing local preorder ids of ending points of \(i\)-th complement edge stored in non-root \\ \hline \(type\_in\) & array showing the \(i\)-th complement edge stored in non-root is 0-edge or not \\ \hline \end{tabular}
\end{table}
Table 1: Components of the top ZDD.  
root of the top DAG stores 0-edge and 1-edge to the terminal \(\top\). Because the height of the top DAG is \(\mathrm{O}(\log n)\), the claim holds.