Compact Data Structures for Collections of Sets

We consider the problem of representing a collection of sets $𝒮=\{S_1,\mathrm{\dots },S_s\}$ from a universe $𝒰$ of size $u$ while supporting basic queries, including retrieving the $k$th element and predecessor and successor queries. The goal is to store the sets compactly while supporting fast queries. This problem has important applications, including the representation of postings lists in inverted indexes and adjacency-list representations of graphs.

To measure space, we often consider the worst-case entropy defined as $H(𝒮)={\sum }_{i=1}^s\lg \left(\genfrac{}{}{0pt}{}{u}{|S_i|}\right)$ as a natural information-theoretic worst-case lower bound on the number of bits needed to store $𝒮$. Using standard techniques [6, 5, 9], we can store $𝒮$ within $H(𝒮)+O(n+s\log n)$ bits and support retrieval (i.e., accessing any $k$th element of any set) in constant time.

In this paper, we propose a finer measure of entropy for $𝒮$ that can take advantage of the fact that some sets may be subsets of others. If $S_i\subset S_j$, we can encode $S_i$ using $\log \left(\genfrac{}{}{0pt}{}{|S_j|}{|S_i|}\right)$ bits, by indicating which elements in $S_j$ are also in $S_i$. We show how to construct a hierarchy from $𝒮$ such that children are subsets of their parent. This leads to a new notion of entropy called the containment entropy, defined as

where $p(S_i)$ is the parent of $S_i$ (see Section 3). It is easy to see that the containment entropy is a finer notion of entropy since $L(𝒮)\le H(𝒮)$. Our main result is that we efficiently represent $𝒮$ in space close to its containment entropy while supporting queries efficiently.

Thus, compared to the above-mentioned standard data structures, we replace the worst-case entropy $H(𝒮)$ with $L(𝒮)$ in our space bound in Theorem 1.

We also obtain several corollaries of Theorem 1. We show how to implement the common operations of set intersection, set union, and set difference. By combining Theorem 1 with techniques from Barbay and Kenyon [2] we obtain fast implementations of these operations in terms of the alternation bound [2] directly on our representation. We also show how to apply Theorem 1 to efficiently store a collection of bitvectors while supporting access, rank, and select queries.

Technically, the result is obtained by constructing a tree structure, where each node represents a set, and children represent subsets of their parent. We then represent each set as a sparse bitvector that indicates which of the elements of the parent are present in the child. This leads to a simple representation that achieves the desired space bound. Unfortunately, if we directly implement a retrieval query on this representation, we have to traverse the path from the set $S$ to the root leading to a query time of $\mathrm{\Omega }(h)$, where $h$ is the height of the tree. We show how to efficiently shortcut paths in the tree without asymptotically increasing the space, yielding the $O(\log (u/|S|))$ time. We then extend these techniques to handle predecessor and successor queries in the same time, leading to the full result of Theorem 1.

A bitvector $B[1..u]$ is a data structure that represents a sequence of $u$ bits and supports the following operations:

• $\mathrm{■}$

  $access(B,i)$ returns $B[i]$, the $i$th bit of $B$.

• $\mathrm{■}$

  $ran{k}_b(B,i)$, where $b\in \{0,1\}$, returns the number of times bit $b$ occurs in the prefix $B[1..i]$ of the bitvector. We assume $ran{k}_b(B,0)=0$.

• $\mathrm{■}$

  $selec{t}_b(B,j)$ returns the position in $B$ of the $j$th occurrence of bit $b\in \{0,1\}$. We assume $selec{t}_b(B,0)=0$ and $selec{t}_b(B,i)=n+1$ if $b$ does not occur $i$ times in $B$.

Note that $ran{k}_0(B,i)=i-ran{k}_1(B,i)$. By default we assume $b=1$. It is possible to represent bitvector $B$ using $u+o(u)$ bits and solve all the operations in $O(1)$ time [3, 8]. If $n$ is the number of 1s in $B$, it is possible [6, 5, 9] to represent $B$ using

bits,¹¹1The formula on the left is zero if $n=0$. so that $selec{t}_1$ is implemented in constant time, while $access$ and $ran{k}_b$ are solved in time $O(1+\log \frac{u}{n})$. Operation $selec{t}_0$ can be solved in time $O(\log n)$ by binary search on $selec{t}_1$. This is called the sparse bitvector representation in this paper.

We note that $\lg \left(\genfrac{}{}{0pt}{}{u}{n}\right)$ is the entropy of the set of positions where $B$ contains $n$ 1s, or equivalently, the entropy of the sets of $n$ elements in a universe of size $u$. We will indistinctly speak of the operations $access$, $rank$, and $select$ over sets $S$ on the universe $[1..u]$, referring to the corresponding bitvector $B$ where $B[i]=1$ iff $i\in S$. For example, $select(S,k)$ is the $k$th smallest element of $S$.

Let $𝒮=\{S_1,S_2,\mathrm{\dots },S_s\}$ be a set of $s$ distinct sets, and $𝒰=S_1\cup S_2\cup \mathrm{\cdots }\cup S_s$ be their union. For simplicity we assume $𝒰=[1..u]$, so $u=|𝒰|$. Let $n_i=|S_i|$ and $n={\sum }_{i=1}^s{n}_i$ be the total size of all sets; note $n\ge u$.

A simple notion of entropy for $𝒮$ is its worst-case entropy

It is not hard to store $𝒮$ within $H(𝒮)+O(n+s\log n)$ bits, by using the sparse bitvector representation of Section 2, which stores each $S_i$ within $\lg \left(\genfrac{}{}{0pt}{}{u}{n_i}\right)+O(n_i+\log u)$ bits, and offers constant-time retrieval of any element of $S_i$ via $select(S_i,k)$. We use $O(s\log n)$ additional bits to address the representations of the $s$ sets.

We now propose a finer measure of entropy for $𝒮$, which exploits the fact that some sets can be subsets of others. If $S_i\subset S_j$, we can describe $S_i$ using $\lg \left(\genfrac{}{}{0pt}{}{n_j}{n_i}\right)$ bits, which indicate which elements of $S_j$ are also in $S_i$. We define a tree structure whose nodes are the sets $S_i$, and the parent of $S_i$, $p(S_i)$, is any smallest $S_j$ such that $S_i\subset S_j$. If $S_i$ is not contained in any other set, then its parent is the tree root, which represents $𝒰$. We then define the following measure of entropy, which we call the containment entropy.

Clearly $L(𝒮)\le H(𝒮)$ because $p_i\le u$ for every $i$. Note that $L(𝒮)$ is arguably the optimal space we can achieve by representing sets as subsets of others in $𝒮$, but we could obtain less space if other arrangements were possible. For example, if many sets are subsets of both $S_i$ and $S_j$, it could be convenient to introduce a new set $S_i\cap S_j$ in the hierarchy, even if it is not in $𝒮$. An advantage of $L(𝒮)$ is that it is easily computed in polynomial time from $𝒮$, whereas more general notions like the one that allows the creation of new sets may be not.

It is not hard to represent $𝒮$ within space close to $L(𝒮)$: we can use the sparse bitvector representation of Section 2 to store each $S_i$ relative to its parent $p(S_i)$, within $\lg \left(\genfrac{}{}{0pt}{}{p_i}{n_i}\right)+O(n_i+\log p_i)$ bits, which add up to $L(𝒮)+O(n+s\log u)$ bits. The problem is that now $select(S_i,k)$ gives the position of the $k$th element of $S_i$ within those of $p(S_i)$, not within $𝒰$, and thus $select(S_i,k)$ is not directly the identity of the $k$th element of $S_i$. In order to obtain the identity of the element, we must compute $select(p(S_i),select(S_i,k))$ and so on, consecutively following the chain of ancestors of $S_i$ until the root $𝒰$; see Algorithm 1. This may take time proportional to the height of the hierarchy, which can be up to $O(s)$. We now show how to reduce this time to logarithmic, by introducing shortcuts in the hierarchy.

We now prove a couple of relevant properties of this contracted hierarchy.

We can build the hierarchical representation by adding one set $S$ at a time, in decreasing order of size, to ensure it is correct to insert $S$ as a leaf. To insert $S$ in $𝒮$, we first find a smallest set $S^{\prime }\in 𝒮$ such that $S\subset S^{\prime }$. The sets that contain $S$ form a connected subgraph of the hierarchy that includes the root. So we can traverse the hierarchy from the root, looking for the lowest nodes that contain $S$, and retain the smallest of those. For each hierarchy node $S_i$ to check, we take each element of $S$ and verify that it exists in $S_i$ via a predecessor query, which takes time $O(\log (u/|S_i|))\subseteq O(\log (u/|S|))$, because $|S|\le |S_i|$. We then find a smallest set $S^{\prime }$ containing $S$ in time $O(s^{\prime }|S|\log (u/|S|))$, where $s^{\prime }\le n/|S|$ is the current number of sets in $𝒮$ and $n$ is its final sum of set sizes.

We then insert $S$ in the hierarchy by setting $p(S)=S^{\prime }$. To find $c(S)$, we find the highest ancestor $S^{\prime \prime }$ of $S^{\prime }$ whose size is $|S^{\prime \prime }|\le 2|S|$ (or let $S^{\prime \prime }=S^{\prime }$ if no such ancestor exists), and set $c(S)=S^{\prime \prime }$. Finally, we build the representation of $S$ relative to $S^{\prime \prime }$, in time $O(|S|)$ [9].

Note that, when we find the ancestor $S^{\prime \prime }$, we traverse the upward path defined by the parent function $p(\cdot )$, not $c(\cdot )$. We still use $c(\cdot )$ during construction to answer the predecessor queries, to determine inclusion of $S$, in logarithmic time.

Combining Lemmas 6, 7, and 10 we have shown Theorem 1.

We have described the containment entropy, a new entropy measure for collections of sets, which is sensitive to subset relationships between sets. To our knowledge, this idea has not before been considered in the vast literature on efficient set representations that has emerged primarily from efficiency concerns in information retrieval systems [11]. One could consider dictionary-based compression of sets (see, e.g., [10, 4]) as implicitly capturing some aspect of subset relationships, but the representations and analysis we have described here consider subset relationships explicitly.

An interesting direction for future work is to explore the practicality of these hierarchical set representations in various application contexts. An immediate concern is that of hierarchy construction. Our initial experiments with a collection of sets taken from the genomic search engine Themisto [1] applied to a set of 16 thousand bacterial genomes (over 80GB of data) indicate that, even for large set collections, hierarchy construction is tractable and scales almost linearly with the total length of the sets in practice. On a collection of 10.55 million sets of average size 3,607 (10.52 million of which were subsets of at least one other set) of more than 38 billion elements in total, we were able to find the smallest super set of every set in less than 40 hours in total, using just 16 threads of execution. The resulting representation used just 0.18 bits per element, compared to the 0.32 bits per element used by Themisto’s representation, which selects between different set representations based on set density.