Compact representations of ordered sets
Daniel K. Blandford, Guy E. Blelloch · 2004
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 pro-duces an ordered set structure supporting the same op-erations in the same time bounds but with O(n log m+nn) 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α log2m) 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. 1