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.