Lower bounds on the size of selection and rank indexes

ABSTRACT

The rank index problem is the following: Preprocess and store a bit string x ∈ {0,1}ⁿ on a random access machine with word size w so that rank queries "What is Σ^ji=1 xi?" for arbitrary values of j can afterwards be easily answered. The selection index problem is the following: Preprocess and store a bit string x ∈ {0,1}ⁿ so that selection queries "What is the index of the j'th 1-bit in x?" for arbitrary values of j can afterwards be easily answered. The data structure representing x should be an index structure, i.e., the n-bit string x is kept verbatim in [n/w] words and the preprocessing phase adds an r-bit index φ(x) with additional information contained in [r/w] words. We are interested in tradeoffs between r, the size of the index measured in bits (the redundancy of the scheme), and t, the worst case time for answering a query.

REFERENCES

• 1: David Richard Clark, Compact pat trees, University of Waterloo, Waterloo, Ont., Canada, 1998
• 2: Erik D. Demaine , Alejandro López-Ortiz, A linear lower bound on index size for text retrieval, Journal of Algorithms, v.48 n.1, p.2-15, August 2003 [doi>10.1016/S0196-6774(03)00043-9]
• 3: Anna Gál, Peter Bro Miltersen. The cell probe complexity of succinct data structures. ICALP 2003, pages 332--344.
• 4: Guy Jacobson. Space-efficient Static Trees and Graphs. FOCS 1989, pages 549--554.
• 5: J. Ian Munro, Tables, Proceedings of the 16th Conference on Foundations of Software Technology and Theoretical Computer Science, p.37-42, December 18-20, 1996
• 6: J. Ian Munro, Space efficient suffix trees, Journal of Algorithms, v.39 n.2, p.205-222, May 2001 [doi>10.1006/jagm.2000.1151]
• 7: Rajeev Raman , Venkatesh Raman , S. Srinivasa Rao, Succinct indexable dictionaries with applications to encoding k-ary trees and multisets, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.233-242, January 06-08, 2002, San Francisco, California