Fast, Small, Simple Rank/Select on Bitmaps

Rank

and

select

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.