###
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.