Compact representations of ordered sets

ABSTRACT

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^α log² 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.

REFERENCES

• 1: The C++ standard template library. http://www.sgi.com/tech/stl/index.html.
• 2: C. R. Aragon and R. G. Seidel. Randomized search trees. In Proc. 30th Annual Symposium on Foundations of Computer Science, pages 540--545, 1989.
• 3: Dan Blandford , Guy Blelloch, Index Compression through Document Reordering, Proceedings of the Data Compression Conference (DCC '02), p.342, April 02-04, 2002
• 4: D. Blandford, G. Blelloch, D. Cardoze, and C. Kadow. Compact representations of simplicial meshes in two and three dimensions. In Proc. 12th International Meshing Roundtable, 2003.
• 5: Andrej Brodnik , J. Ian Munro, Membership in Constant Time and Almost-Minimum Space, SIAM Journal on Computing, v.28 n.5, p.1627-1640, April/May 1999 [doi>10.1137/S0097539795294165]
• 6: A. L. Buchsbaum, R. Sundar, and R. E. Tarjan. Data structural bootstrapping, linear path compression, and catenable heap ordered double ended queues. In Proc. 33rd IEEE Symp. on Foundations of Computer Science, pages 40--49, 1992.
• 7: Svante Carlsson , Christos Levcopoulos , Ola Petersson, Sublinear merging and natural merge sort, Proceedings of the international symposium on Algorithms, p.251-260, August 1990, Tokyo, Japan
• 8: P. Elias. Universal codeword sets and representations of the integers. IEEE Transactions on Information Theory, IT-21(2):194--203, March 1975.
• 9: L. J. Guibas and R. Sedgewick. A dichromatic framework for balanced trees. In Proc. 19th IEEE Symposium on Foundations of Computer Science, pages 8--21, 1978.
• 10: Haim Kaplan , Robert E. Tarjan, Purely functional representations of catenable sorted lists, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.202-211, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237865]
• 11: A. Moffat, O. Petersson, and N. C. Wormald. A tree-based mergesort. Acta Informatica, 35(9):775--793, 1998.
• 12: Alistair Moffat , Lang Stuiver, Binary Interpolative Coding for Effective Index Compression, Information Retrieval, v.3 n.1, p.25-47, July 2000 [doi>10.1023/A:1013002601898]
• 13: L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford Digital Library Technologies Project, 1998.
• 14: R. Pagh. Low redundancy in static dictionaries with O(1) worst case lookup time. Lecture Notes in Computer Science, 1644:595--??, 1999.
• 15: William Pugh, Skip Lists: A Probabilistic Alternative to Balanced Trees, Proceedings of the Workshop on Algorithms and Data Structures, p.437-449, August 17-19, 1989
• 16: R. Seidel and C. R. Aragon. Randomized search trees. Algorithmica, 16(4/5):464--497, 1996.
• 17: I. H. Witten, A. Moffat, and T. C. Bell. Managing Gigabytes. Morgan Kaufman, 1999.