Rajeev Raman
Abstract
We consider the indexable dictionary problem, which consists of storing a set S ⊆ {0,…,m − 1} for some integer m while supporting the operations of rank(x), which returns the number of elements in S that are less than x if x ∈ S, and −1 otherwise; and select(i), which returns the ith smallest element in S. We give a data structure that supports both operations in O(1) time on the RAM model and requires B(n, m) + o(n) + O(lg lg m) bits to store a set of size n, where B(n, m) = ⌊lg (m/n)⌋ is the minimum number of bits required to store any n-element subset from a universe of size m. Previous dictionaries taking this space only supported (yes/no) membership queries in O(1) time. In the cell probe model we can remove the O(lg lg m) additive term in the space bound, answering a question raised by Fich and Miltersen [1995] and Pagh [2001].
We present extensions and applications of our indexable dictionary data structure, including:
—an information-theoretically optimal representation of a k-ary cardinal tree that supports standard operations in constant time;
—a representation of a multiset of size n from {0,…,m − 1} in B(n, m + n) + o(n) bits that supports (appropriate generalizations of) rank and select operations in constant time; and + O(lg lg m)
—a representation of a sequence of n nonnegative integers summing up to m in B(n, m + n) + o(n) bits that supports prefix sum queries in constant time.
- Aho, A. V., Hopcroft, J. E., and Ullman, J. D. 1983. Data Structures and Algorithms. Addison-Wesley. Google Scholar
Digital Library
- Ajtai, M., Fredman, M. L., and Komlós, J. 1984. Hash functions for priority queues. Inf. Control 63, 3, 217--225. Google ScholarDigital Library
- Andersson, A., Hagerup, T., Nilsson, S., and Raman, R. 1998. Sorting in linear time? J. Comput. Syst. Sci. 57, 1, 74--93. Google ScholarDigital Library
- Beame, P. and Fich, F. E. 2002. Optimal bounds for the predecessor problem and related problems. J. Comput. Syst. Sci. 65, 1, 38--72. Google ScholarDigital Library
- Benoit, D., Demaine, E. D., Munro, J. I., Raman, R., Raman, V., and Rao, S. S. 2005. Representing trees of higher degree. Algorithmica 43, 4, 275--292. Google ScholarDigital Library
- Brodnik, A. and Munro, J. I. 1999. Membership in constant time and almost-minimum space. SIAM J. Comput. 28, 5, 1627--1640. Google ScholarDigital Library
- Clark, D. R. 1996. Compact pat trees. Ph.D. thesis, University of Waterloo. Google ScholarDigital Library
- Cleary, J. G. 1984. Compact hash tables using bidirectional linear probing. IEEE Trans. Comput. 33, 9, 828--834. Google ScholarDigital Library
- Darragh, J. J., Cleary, J. G., and Witten, I. H. 1993. Bonsai: A compact representation of trees. Softw. Pract. Exper. 23, 3, 277--291. Google ScholarDigital Library
- Elias, P. 1974. Efficient storage and retrieval by content and address of static files. J. ACM 21, 2, 246--260. Google ScholarDigital Library
- Ferragina, P. and Manzini, G. 2005. Indexing compressed text. J. ACM 52, 4, 552--581. Google ScholarDigital Library
- Fich, F. E. and Miltersen, P. B. 1995. Tables should be sorted (on random access machines). In Proceedings of the 4th International Workshop on Algorithms and Data Structures. Lecture Notes in Computer Science, vol. 955. Springer, 482--493. Google ScholarDigital Library
- Fredman, M. L., Komlós, J., and Szemerédi, E. 1984. Storing a sparse table with O(1) worst case access time. J. ACM 31, 3, 538--544. Google ScholarDigital Library
- Fredman, M. L. and Saks, M. E. 1989. The cell probe complexity of dynamic data structures. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing. ACM, 345-- 354. Google ScholarDigital Library
- Fredman, M. L. and Willard, D. E. 1993. Surpassing the information theoretic bound with fusion trees. J. Comput. Syst. Sci. 47, 3, 424--436. Google ScholarDigital Library
- Geary, R. F., Raman, R., and Raman, V. 2006. Succinct ordinal trees with level-ancestor queries. ACM Trans. Alg. 2, 4, 510--534. Google ScholarDigital Library
- Golynski, A., Munro, J. I., and Rao, S. S. 2006. Rank/Select operations on large alphabets: A tool for text indexing. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM Press, New York, 368--373. Google ScholarDigital Library
- Graham, R. L., Knuth, D. E., and Patashnik, O. 1994. Concrete Mathematics. Addison-Wesley. Google ScholarDigital Library
- Grossi, R., Gupta, A., and Vitter, J. S. 2003. High-Order entropy-compressed text indexes. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA). Society for Industrial and Applied Mathematics, Philadelphia, PA, 841--850. Google ScholarDigital Library
- Grossi, R. and Vitter, J. S. 2005. Compressed suffix arrays and suffix trees with applications to text indexing and string matching. SIAM J. Comput. 35, 2, 378--407. Google ScholarDigital Library
- Hagerup, T. 1998. Sorting and searching on the word RAM. In Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 1373. Springer, 366--398. Google ScholarDigital Library
- Hagerup, T. and Tholey, T. 2001. Efficient minimal perfect hashing in nearly minimal space. In Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 2010. Springer, 317--326.Google Scholar
- Jacobson, G. 1989. Succinct static data structures. Ph.D. thesis, Carnegie Mellon University. Google ScholarDigital Library
- Jansson, J., Sadakane, K., and Sung, W.-K. 2007. Ultra-Succinct representation of ordered trees. In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms. Google ScholarDigital Library
- Munro, J. I. 1996. Tables. In Proceedings of the 16th Conference on Foundations of Software Technology and Theoretical Computer Science. Lecture Notes in Computer Science, vol. 1180. Springer, 37--42. Google ScholarDigital Library
- Munro, J. I. and Raman, V. 2001. Succinct representation of balanced parentheses and static trees. SIAM J. Comput. 31, 3, 762--776. Google ScholarDigital Library
- Munro, J. I., Raman, V., and Rao, S. S. 2001. Space efficient suffix trees. J. Alg. 39, 2, 205--222. Google ScholarDigital Library
- Navarro, G. and Mäkinen, V. 2007. Compressed full-text indexes. ACM Computing Surveys 39, 1, 2. Google ScholarDigital Library
- Pagh, R. 2001. Low redundancy in static dictionaries with constant query time. SIAM J. Comput. 31, 2, 353--363. Google ScholarDigital Library
- Paul, W. J. and Simon, J. 1980. Decision trees and random access machines. In Proceedings of the International Symposium on Logic and Algorithmic, 331--340.Google Scholar
- Raman, R., Raman, V., and Rao, S. S. 2002. Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 233--242. Google ScholarDigital Library
- Raman, V. and Rao, S. S. 1999. Static dictionaries supporting rank. In Proceedings of the 10th International Symposium on Algorithms and Computation. Lecture Notes in Computer Science, vol. 1741. Springer, 18--26.Google Scholar
- Schmidt, J. P. and Siegel, A. 1990. The spatial complexity of oblivious k-probe hash functions. SIAM J. Comput. 19, 5, 775--786. Google ScholarDigital Library
- Tarjan, R. E. and Yao, A. C.-C. 1979. Storing a sparse table. Commun. ACM 22, 11, 606--611. Google ScholarDigital Library
- Yao, A. C.-C. 1981. Should tables be sorted? J. ACM 28, 3, 615--628. Google ScholarDigital Library
Index Terms
- Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets
Recommendations
Succinct indexable dictionaries with applications to encoding k-ary trees and multisets
SODA '02: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithmsWe consider the indexable dictionary problem which consists in storing a set S ⊆ {0,…, m - 1} for some integer m, while supporting the operations of rank(x), which returns the number of elements in S that are less than x if x ε S, and -1 otherwise; and ...
Optimal deterministic approximate parallel prefix sums and their applications
ISTCS '95: Proceedings of the 3rd Israel Symposium on the Theory of Computing Systems (ISTCS'95)Abstract: We show that extremely accurate approximation to the prefix sums of a sequence of n integers can be computed deterministically in O(log log n) time using O(n/log log n) processors in the COMMON CRCW PRAM model. This complements randomized ...
A Residue Number System on Reconfigurable Mesh with Applications to Prefix Sums and Approximate String Matching
Several new number representations based on a Residue Number System are presented which use the smallest prime numbers as moduli and are suited for parallel computations on a reconfigurable mesh architecture. The bit model of linear reconfigurable mesh ...
Comments