Roaring Bitmaps: Implementation of an Optimized Software Library

[Weijun-H]

Abstract

Bitmap indexes are commonly used in databases and search engines. By exploiting bit-level parallelism, they can significantly accelerate queries. However, they can use much memory. Thus we might prefer compressed bitmap indexes. Following Oracle’s lead, bitmaps are often compressed using run-length encoding (RLE). In this work, we introduce a new form of compressed bitmaps called Roaring, which uses packed arrays for compression instead of RLE. We compare it to two high-performance RLE-based bitmap encoding techniques: WAH (Word Aligned Hybrid compression scheme) and Concise (Compressed ‘n’ Composable Integer Set). On synthetic and real data, we find that Roaring bitmaps (1) often compress significantly better (e.g.,2×) and (2) are faster than the compressed alternatives (up to 900× faster for intersections).