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.