Compact representations of ordered sets

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