# DenseZDD: A Compact and Fast Index for Families of Sets +
## 4 ZDD Operations
### sample\((i)\)
As an initial state, we consider the range \((l=-1,h=\mathit{index}(i)]\) as candidates. Next, we divide this range by finding a node with index less than or equal to \(c=\lfloor l+h+1\rfloor/2\). Such a node can be found by \(\mathit{topset}(i,c)\). Recall that \(\mathit{topset}(i,d):=\mathit{rank}_{1}(M,\mathit{level\_ancestor}(U,\mathit{ select}_{1}(M,i),d))\). It is the real preorder rank of a node whose index is less than \(c\) or equal to \(c\). If the index of the found node is less than or equal to \(l\), we update \(l\) by \(l\gets c\) and repeat the execution of _topset_. When a node with index \(x\), \(l<x\leq h\), is found, we choose either \((l,c]\) or \((c,h]\) as a next candidate range for further binary search. We know the cardinality of nodes with indices \(h\), \(c\), and \(l\). The cardinality \(card\) of the family of sets we consider now is the cardinality of the node with index \(h\) minus the cardinality of the node with index \(l\). Then, generate a random integer \(r\in[0,card)\). If \(r\) is less than the cardinality of the node with index \(c\), update \(h\) by \(h\gets c\). Otherwise, update \(l\) by \(l\gets c\). We continue this procedure until \(l+1=h\). After that, we choose the index \(h\) as an element of the output set, and go to the 1-child of the node with index \(h\). Again, we start binary search on the next nodes connected by continuous 0-edges. This algorithm stops when it reaches the 1-terminal node. ```
1:\(idx_{i}\leftarrow\mathit{index}(i)\), \(j\leftarrow-1\), \(idx_{j}\leftarrow-1\);
2:\(card_{j}=0\);
3:while\(idx_{i}\
eq\mathit{idx}_{j}\)do
4:if\(idx_{i}=0\)then
5:return\(\emptyset\);
6:endif
7:\(idx_{k}\leftarrow\lfloor(idx_{i}+idx_{j}+1)/2\rfloor\);
8:\(k\gets\mathit{topset}(i,idx_{k})\);
9:if\(j=k\)then
10:\(j\gets k\);
11:continue;
12:endif
13: Generate an integer \(r\in[0,C[i]+\mathit{empflag}-card_{j})\) uniformly and randomly. 14:if\(r<C[j]+\mathit{empflag}-card_{j}\)then\(\triangleright\)\(idx_{j},idx_{k}\) is chosen
15:\(i\gets k\);
16:\(idx_{i}\leftarrow idx_{k}\);
17:else\(\triangleright\)\(idx_{k},idx_{i}\) is chosen
18:\(j\gets k\);
19:\(idx_{j}\leftarrow idx_{k}\);
20:\(card_{j}\gets card_{j}+C[k]\);
21:if\(\mathit{empflag}=1\)then
22:\(card_{j}\gets card_{j}-1\);
23:\(\mathit{empflag}\gets 0\);
24:endif
25:endif
26:endif
27:\(i_{1}\gets one(i)\);
28:if\(i_{1}\leq 0\)then
29:return\(\{idx_{i}\}\cup\)Random_bin\((abs(i_{1}),1)\);
30:else
31:return\(\{idx_{i}\}\cup\)Random_bin\((abs(i_{1}),0)\);
32:endif
```  
**Algorithm 6**\(\textbf{Random\_bin}(i,\mathit{empflag})\): Algorithm that returns a set uniformly and randomly chosen from the family of sets represented by the ZDD whose root is node \(i\). This algorithm chooses the index by binary search on nodes linked by 0-edges. This algorithm takes \(\mathcal{O}(\log n)\) time to choose one element of an output. The time complexity of this algorithm is \(\mathcal{O}(n\log n)\). This looks worse than the previous algorithm. However, this can be better for set families consisting of small sets. Let \(s\) be the size of the largest sets in the family. Then, its time complexity is \(\mathcal{O}(s\log n)\). Therefore, this algorithm is efficient for large data sets consisting of small sets of many items.