Fast, Small, Simple Rank/Select on Bitmaps
Gonzalo Navarro and Eliana Providel
Rankselect queries on bitmaps are
fundamental for the construction of a variety of compact data
structures. Both can, in theory, be answered in constant time by
spending o(n) extra bits on top of the original bitmap, of length
n, or of a compressed version of it.
However, while the solution for rank is indeed simple and
practical, a similar result for select has been elusive, and
practical compact data structure implementations avoid its use
whenever possible. In addition, the overhead of the o(n)
extra bits is in many cases very significant.
In this paper we bridge the gap between theory and practice by presenting
two structures, one using the bitmap in plain form
and another using a compressed form, that are simple to
implement and combine much lower space overheads than previous work
with excellent time performance for rank and select queries. In
particular, our structure for plain bitmaps is far smaller and faster
for select than any previous structure, while competitive for
rank with the best previous structures of similar size.