10.1184/R1/6604220.v1
Daniel K. Blandford
Daniel K.
Blandford
Guy E. Blelloch
Guy E.
Blelloch
Compact Representations of Ordered Sets
Carnegie Mellon University
1984
computer sciences
1984-01-01 00:00:00
Journal contribution
https://kilthub.cmu.edu/articles/journal_contribution/Compact_Representations_of_Ordered_Sets/6604220
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.