# Better bitmap performance with Roaring bitmaps

arXiv: https://arxiv.org/abs/1402.6407 · HTML: https://mlsanity.com/paper/1402.6407/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Feb 2014.

## Built on by (most cited first, 3 of 3)

- [GraphMineSuite: Enabling High-Performance and Programmable Graph Mining Algorithms with Set Algebra](https://mlsanity.com/paper/2103.03653/) (2021)
- [The P-Completeness of Inverted Index Traversal: On the Complexity of Evaluating Boolean Query DAGs](https://mlsanity.com/paper/2601.18747/) (2026)
- [Query-based versus resource-based cache strategies in tag-based browsing systems](https://mlsanity.com/paper/2501.15481/) (2025)

## Abstract (arXiv)

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, and thus we might prefer compressed bitmap indexes. Following Oracle's lead, bitmaps are often compressed using run-length encoding (RLE). Building on prior work, we introduce the Roaring compressed bitmap format: it 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 times) and (2) are faster than the compressed alternatives (up to 900 times faster for intersections). Our results challenge the view that RLE-based bitmap compression is best.