Compact Representations of Ordered Sets

We consider the problem of efficiently representing sets S of size n from an ordered universe U = {0,...,m-1}. Given any ordered dictionary structure (or comparison-based ordered set structure) D that uses O(n) pointers, we demonstrate a simple blocking technique that produces an ordered set structure supporting the same operations in the same time bounds but with O(n log m+n/n) bits. This is within a constant factor of the information-theoretic lower bound. We assume the unit cost RAM model with word size Ω(log |U|) and a table of size O(mα log2 m) bits, for some constant α > 0. The time bound for our operations contains a factor of 1/α.We present experimental results for the STL (C++ Standard Template Library) implementation of Red-Black trees, and for an implementation of Treaps. We compare the implementations with blocking and without blocking. The blocking variants use a factor of between 1.5 and 10 less space depending on the density of the set