Partial Integers

Bits as part of integers

In this module, we return to the problem of implementing an SSet. The difference now is that we assume the elements stored in the SSet are $w$-bit integers. That is, we want to implement add(x), remove(x), and find(x) where $x \in \{0,...,2^w−1\}$. It is not too hard to think of plenty of applications where the data—or at least the key that we use for sorting the data—is an integer.

We discuss three data structures, each building on the ideas of the previous. The first structure, the BinaryTrie performs all three SSet operations in $O(w)$ time. This is not very impressive, since any subset of $\{0,...,2^w − 1\}$ has size $n \leq 2^w$ , so that $log\space n \leq w$. The other SSet implementations perform all operations in $O(\log n)$ time so they are all at least as fast as a BinaryTrie.

The second structure, the XFastTrie, speeds up the search in a BinaryTrie by using hashing. With this speedup, the find(x) operation runs in $O(\log w)$ time. However, add(x) and remove(x) operations in an XFastTrie still take $O(w)$ time and the space used by an XFastTrie is $O(n \cdot w)$.

The third data structure, the YFastTrie, uses an XFastTrie to store only a sample of roughly one out of every w elements and stores the remaining elements in a standard SSet structure. This trick reduces the running time of add(x) and remove(x) to $O(\log w)$ and decreases the space to $O(n)$.

The implementations used as examples can store any type of data, as long as an integer can be associated with it. In the code samples, the variable ix is always the integer value associated with x, and the method in.intValue(x) converts x to its associated integer. In the text, however, we will simply treat x as if it is an integer.