Lower bounds on the size of selection and rank indexes
Peter Bro Miltersen · Symposium on Discrete Algorithms · 2005
The rank index problem is the following: Preprocess and store a bit string x ∈ {0,1}n on a random access machine with word size w so that rank queries What is Σji=1xi? 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}n 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.