# Storing Set Families More Compactly with Top ZDDs
## 2 Preliminaries
### Zero-Suppressed Binary Decision Diagrams  
Zero-suppressed Binary Decision Diagrams (ZDDs) [1] are data structures for manipulating finite set families. A ZDD is a directed acyclic graph (DAG) \(G=(V,E)\) with a root node satisfying the following properties. A ZDD has two types of nodes; branching nodes and terminal nodes. There are exactly two terminal nodes; \(\bot\) and \(\top\). These terminal nodes have no outgoing edges. Each branching node \(v\) has an integer label \(\ell(v)\in\{1,\ldots,c\}\), and also has two outgoing edges 0-edge and 1-edge. The node pointed to by the 0-edge (1-edge) of \(v\) is denoted by \(v_{0}=zero(v)\) (\(v_{1}=one(v)\)). If for any branching node \(v\) it holds \(\ell(v)<\ell(v_{0})\) and \(\ell(v)<\ell(v_{1})\), then the ZDD is said to be ordered. In this paper, we consider only ordered ZDDs. For convenience, we assume \(\ell(v)=c+1\) for terminal nodes \(v\). We divide the nodes of the ZDD into layers \(L_{1},\ldots,L_{c+1}\) Note that if \(i\geq j\) there are no edges from layer \(L_{i}\) to layer \(L_{j}\). The number of nodes in ZDD \(G\) is denoted by \(|G|\) and called the size of the ZDD. On the other hand, the data size of a ZDD stands for the number of bits used in the data structure representing the ZDD.  
In a ZDD, each node represents a set family. When a ZDD is single-rooted, the set family represented by the root is called the set family represented by the ZDD. The set family represented by a ZDD is defined as follows.  
**Definition 1** (The set family represented by a ZDD).: _Let \(v\) be a node of a ZDD and \(v_{0}=zero(v)\), \(v_{1}=one(v)\). Then the set family \(\mathcal{F}_{v}\) represented by \(v\) is defined as follows. ZDD \(G=(V,E)\), rooted at node \(v\in V\), represents a finite family of sets \(\mathcal{F}_{v}\) on \(C\) defined recursively as follows:_  
1. _If_ \(v\) _is a terminal node: if_ \(v=\top\)_,_ \(\mathcal{F}_{v}=\{\emptyset\}\)_, if_ \(v=\bot\)_,_ \(\mathcal{F}_{v}=\emptyset\)_._
2. _If_ \(v\) _is a branching node:_ \(\mathcal{F}_{v}=\{S\cup\{\ell(v)\}\mid S\in\mathcal{F}_{v_{1}}\}\cup\mathcal{ F}_{v_{0}}\)_._  
For the root node \(r\) of ZDD \(G\), \(\mathcal{F}_{r}\) corresponds to the set family represented by the ZDD \(G\). This set family is also denoted by \(\mathcal{F}_{G}\).  
A family of sets can be represented by a binary tree as shown in Figure 1. Let \(\mathcal{F}\) be a family of sets. For a set \(S\), we traverse the 1-edge at the nodes whose labels are elements in \(S\), and the 0-edge otherwise. Then we reach the \(\top\) if \(S\in\mathcal{F}\), and the \(\bot\) otherwise. Any family of sets can be represented by a binary tree of height \(c\). This is almost equivalent to the bitstring representation of length \(2^{n}\). This tree structure can be used for compression, however. A ZDD can be constructed by deleting redundant nodes from the binary tree and merging equivalent nodes. Every path from the root to the terminal \(\top\) on ZDD \(G\) have a one-to-one correspondence to a set \(S=\{a_{1},\ldots,a_{|S|}\}\) in the set family represented by \(G\). Consider a traversal of nodes from the root towards terminals so that for each branching node \(v\) on the path, if \(\ell(v)\
ot\in S\) we go to \(v_{0}=zero(v)\) from \(v\), and if \(\ell(v)\in S\) we go to \(v_{1}=one(v)\) from \(v\). By repeating this process, if \(S\in\mathcal{F}_{G}\) we arrive at \(\top\), and if \(S\
ot\in\mathcal{F}_{G}\) we arrive at \(\bot\) or find no branching node corresponding to some \(a_{i}\in S\) during the process. An example is shown in Figure 2. ZDDs also support various set operations, which can be used to obtain new ZDDs from multiple ZDDs, as shown in Figure 3.