Optimal lower bounds for rank and select indexes

AbstractWe develop a new lower bound technique for data structures. We show an optimal Ω(nlglgn/lgn) space lower bounds for storing an index that allows to implement rank and select queries on a bit vector B provided that B is stored explicitly. These results improve upon [Peter Bro Miltersen, Lower bounds on the size of selection and rank indexes, in: Proceedings of the 16th Annual ACM–SIAM Symposium on Discrete Algorithms, 2005, pp. 11–12]. We show Ω((m/t)lgt) lower bounds for storing rank/select index in the case where B has m 1-bits in it and the algorithm is allowed to probe t bits of B. We also present an improved data structure that implements both rank and select queries with an index of size (1+o(1))(nlglgn/lgn)+O(n/lgn), that is, compared to existing results we give an explicit constant for storage in the RAM model with word size lgn. An advantage of this data structure is that both rank and select indexes share the most space consuming part of order Θ(nlglgn/lgn) making it more practical for implementation