# DenseZDD: A Compact and Fast Index for Families of Sets +
## 2 Preliminaries
### Zero-suppressed Binary Decision Diagrams  
A _zero-suppressed binary decision diagram_ (ZDD) [2] is a variant of a binary decision diagram [1], customized to manipulate finite families of sets. A ZDD is a directed acyclic graph satisfying the following. A ZDD has two types of nodes, terminal and nonterminal nodes. A _terminal node_\(v\) has as an attribute a value \(value(v)\in\{0,1\}\), indicating whether it is the _0-terminal node_ or the _1-terminal node_, denoted by \(\mathbf{0}\) and \(\mathbf{1}\), respectively. A _nonterminal node_\(v\) has as attributes an integer \(index(v)\in\{1,\ldots,n\}\) called the _index_, and two children \(zero(v)\) and \(one(v)\), called the _0-child_ and _1-child_. The edge from a nonterminal to its 0-child (1-child resp.) is called the _0-edge_ (_1-edge_ resp.). In the figures in the paper, terminal and nonterminal nodes are drawn as squares and circles, respectively, and 0-edges and 1-edges are drawn as dotted and solid arrows, respectively. We define \(triple(v)=\langle index(v),zero(v),one(v)\rangle\), called the _attribute triple_ of \(v\). For any nonterminal node \(v\), \(index(v)\) is larger than the indices of its children (In ordinary BDD or ZDD papers, the indices are in ascending order from roots to terminals. For convenience, we employ the opposite ordering in this paper).We define the _size_ of a ZDD \(G\) as the number of its nonterminals and denote it by \(|G|\). **Definition 1** (set family represented by a ZDD). : _A ZDD \(G=(V,E)\) rooted at a node \(v\in V\) represents a finite family of sets \(F(v)\) on \(U_{n}\) defined recursively as follows: (1) If \(v\) is a terminal node: \(F(v)=\{\emptyset\}\) if \(value(v)=1\), and \(F(v)=\emptyset\) if \(value(v)=0\). (2) If \(v\) is a nonterminal node, then \(F(v)\) is the finite family of sets \(F(v)=(\{\{e_{index(v)}\}\}\sqcup F(one(v)))\cup F(zero(v))\)._  
The example in Figure 1 represents a family of sets \(F=\{\{\{6,5,4,3\},\{6,5,4,2\},\{6,5,4,1\},\{6,5,4\},\{6,5,2\},\{6,5,1\},\{6,5 \},\{6,4,3,2\},\{6,4,3,1\},\{6,4,2,1\},\{6,2,1\},\{3,2,1\}\}\). A set \(S=\{c_{1},\ldots,c_{\ell}\}\) describes a path in the graph \(G\) starting from the root in the following way: At each nonterminal node with label \(c_{i}\), the path continues to the 0-child if \(c_{i}\
ot\in S\) and to the 1-child if \(c_{i}\in S\), and the path eventually reaches the 1-terminal (0-terminal resp. ), indicating that \(S\) is accepted (rejected resp). We employ the following two reduction rules, shown in Figure 2, to compress ZDDs: (a) Zero-suppress rule: A nonterminal node whose 1-child is the 0-terminal node is deleted; (b) sharing rule: two or more nonterminal nodes having the same attribute triple are merged. By applying the above rules, we can reduce the size of the graph without changing its semantics. If we apply the two reduction rules as much as possible, then we obtain the canonical form for a given family of sets. We implement the sharing rule by using a hash table such that a key is an attribute triple and the value of the key is the pointer to the node corresponding to the attribute triple. When we want to create a new node with an attribute triple \(\langle i,v_{0},v_{1}\rangle\), we check whether such a node has already existed or not. If such a node exists, we do not create a new node and use the node. Otherwise, we create a new node  
Figure 1: Example of ZDD. with \(\langle i,v_{0},v_{1}\rangle\) and we register it to the hash table. After that, \(V\) and \(E\) are updated to \(V\cup\{v\}\) and \(E\cup\{(v,v_{0}),(v,v_{1})\}\), respectively. We can further reduce the size of ZDDs by using a type of _attributed edges_[2; 10], named _0-element edges_. A _ZDD with 0-element edges_ is defined as follows. A ZDD with 0-element edges has the same property as an ordinary ZDD, except that it does not have the 1-terminal and that the 1-edge of each nonterminal node has as an attribute a one bit flag, called _\(\emptyset\)-flag_.