# DenseZDD: A Compact and Fast Index for Families of Sets +
## 2 Preliminaries
### Problem of Existing ZDDs  
Existing ZDD implementations (supporting dynamic operations) have the following problem in addition to the size of representations discussed in Section 1. The \(\mathit{member}(v,S)\) operation needs \(\Theta(n)\) time in the worst case. In practice, the sizes of query sets are often much smaller than \(n\), so an \(\mathcal{O}(|S|)\) time algorithm is desirable. Existing implementations need \(\Theta(n)\) time for the \(\mathit{member}(v,S)\) operation because it is implemented by repeatedly using the \(\mathit{zero}(v)\) operation.  
For example, we traverse 0-edges 255 times when we search \(S=\{e_{1}\}\) on the ZDD for \(F=\{\{e_{1}\},\ldots,\{e_{256}\}\}\). If we translate the ZDD to an equivalent automaton by using an array to store pointers (see Figure 4), we can execute the searching in \(\mathcal{O}(|S|)\) time. ZDD nodes correspond to labeled edges in the automaton. However, the size of such an automaton via straightforward translation can be \(\Theta(n)\) times larger than the original ZDD [11] in the worst case. Therefore, we want to perform \(\mathit{member}(v,S)\) operations in \(\mathcal{O}(|S|)\) time on ZDDs.  
\begin{table}
\begin{tabular}{l l} \hline \hline \(\mathit{index}(v)\) & Returns the index of node \(v\). \\ \(\mathit{zero}(v)\) & Returns the 0-child of node \(v\). \\ \(\mathit{one}(v)\) & Returns the 1-child of node \(v\). \\ \(\mathit{getnode}(i,v_{0},v_{1})\) & Generates (or makes a reference to) a node \(v\) \\  & with index \(i\) and two child nodes \(v_{0}=\mathit{zero}(v)\) and \(v_{1}=\mathit{one}(v)\). \\ \(\mathit{topset}(v,i)\) & Returns a node with the index \(i\) reached by traversing only 0-edges from \(v\). \\  & If such a node does not exist, it returns the 0-terminal node. \\ \(\mathit{member}(v,S)\) & Returns _true_ if \(S\in F(v)\), and returns _false_ otherwise. \\ \(\mathit{count}(v)\) & Returns \(|F(v)|\). \\ \(\mathit{sample}(v)\) & Returns a set \(S\in F(v)\) uniformly and randomly. \\ \(\mathit{offset}(v,i)\) & Returns \(u\) such that \(F(u)=\{\ S\subseteq U_{n}\ |\ S\in F,e_{i}\
ot\in S\}\). \\ \(\mathit{onset}(v,i)\) & Returns \(u\) such that \(F(u)=\{\ S\backslash\{e_{i}\}\subseteq U_{n}\ |\ S\in F,e_{i}\in S\}\). \\ \(\mathit{apply}_{v}(v_{1},v_{2})\) & Returns \(v\) such that \(F(v)=F(v_{1})\circ F(v_{2})\), for \(\circ\in\{\cup,\cap,\setminus\oplus\}\). \\ \hline \hline \end{tabular}
\end{table}
Table 1: Main operations supported by ZDD. The first group are the primitive ZDD operations used to implement the others, yet they could have other uses.  
Figure 4: Worst-case example of a straightforward translation.  
[PERSON] proposed Z-Skip Links [12] to accelerate the traversal of ZDDs of large-scale sparse datasets. Their method adds one link per node to skip nodes that are concatenated by 0-edges. Therefore, the amount of memory requirement cannot be smaller than original ZDDs. Z-Skip-Links make the membership operations much faster than using conventional ZDD operations when handling large-scale sparse datasets. However, the computation time is probabilistically analyzed only for the average case.