# DenseZDD: A Compact and Fast Index for Families of Sets +
## 6 Hybrid Method  
In this section, we show how to implement dynamic operations on DenseZDD. Namely, we implement the \(getnode(i,v_{0},v_{1})\) operation. Our approach is to use a hybrid data structure using both the DenseZDD and a conventional dynamic ZDD. Assume that initially all the nodes are represented by a DenseZDD. Let \(m_{0}\) be the number of initial nodes. In a conventional dynamic ZDD, the operation \(getnode(i,v_{0},v_{1})\) is implemented by a hash table indexed with the triple \(\langle i,v_{0},v_{1}\rangle\).  
We first show how to check whether the node \(v:=getnode(i,v_{0},v_{1})\) has already existed or not. That is, we want to find a node \(v\) such that \(index(v)=i\), \(zero(v)=v_{0}\), \(one(v)=v_{1}\). If \(v\) exists in the zero-edge tree, \(v\) is one of the \(0^{*}\)-children of \(v_{0}\). Consider again the subtree of the zero-edge tree rooted at \(v_{0}\) and the \(0^{*}\)-children of \(v_{0}\) (see the right of Figure 5). Let \(d_{p}\) be the (possibly dummy) parent of \(v\) in the zero edge tree. The parent of all the \(0^{*}\)-children of \(v_{0}\) with index \(i\) in the zero edge tree is also \(d_{p}\). The node \(d_{p}\) is located on the path from \(v_{0}\) to the first node, say \(v_{t}\), among the \(0^{*}\)-children of \(v_{0}\) (note that since the zero edge tree is an ordered tree, we can well-define the \"first\" node). That is, \(d_{p}\) is an ancestor of \(v_{t}\). Since the position of \(v_{t}\) is the next of the position of \(v_{0}\) in \(M\) (in the preorder), we can obtain the position of \(v_{t}\) by \(select_{1}(M,rank_{1}(M,v_{0})+1)\). Noting that the index of \(d_{p}\) is \(i-1\), we obtain the position of \(d_{p}\) by \(d_{p}=level\_ancestor(U,select_{1}(M,rank_{1}(M,v_{0})+1),i-1)\). Our task is to find thenode \(v\) such that \(one(v)=v_{1}\) among the children of \(d_{p}\). Since the \(0^{\prime}\)-children \(v^{\prime}\) of \(d_{p}\) are sorted in the lexicographic order of \(\langle index(v^{\prime}),prank(one(v^{\prime}))\rangle\) values by the construction algorithms, we can find \(v\) by a binary search. For this, we use the _degree_ and _child_ operations on the zero-edge tree (recall that _degree_ is used for obtaining the number of children of a node).  
If \(v\) does not exist, we create such a node and register it to the hash table as well as a dynamic ZDD. Note that we do not update the DenseZDD, and thus if we want to treat the ZDD, say \(Z_{\text{new}}\), whose root is the new node as the DenseZDD, we need to construct the DenseZDD structure for \(Z_{\text{new}}\).  
We obtain the following theorem on the time complexity.  
Theorem 4.1: _The existence of \(\text{getnode}(i,v_{0},v_{1})\) can be checked in \(\mathcal{O}(t\log m)\) time, where \(t\) is the time complexity of primitive ZDD operations._  
If the BP sequence is not compressed, _getnode_ takes \(\mathcal{O}(\log m)\) time; otherwise it takes \(\mathcal{O}(\log^{2}m)\) time. By discussion similar to the proofs of Theorems 2.1 and 2.1 in Section 5, we have the following theorems.  
Theorem 4.2: _A ZDD with \(m\) nodes on \(n\) items can be stored in \(2u+m\log m+3m+o(u)\) bits so that the \(\text{getnode}(i,v_{0},v_{1})\) operation is done in \(\mathcal{O}(\log m)\) time, where \(u\) is the number of real and dummy nodes in the zero edge tree of \(DZ(Z)\)._  
Theorem 4.3: _A ZDD with \(m\) nodes on \(n\) items can be stored in \(\mathcal{O}(m(\log m+\log n))\) bits so that the \(\text{getnode}(i,v_{0},v_{1})\) operation is done in \(\mathcal{O}(\log^{2}m)\) time._