# Consistently faster and smaller compressed bitmaps with Roaring

**Authors:** Daniel Lemire, Gregory Ssi-Yan-Kai, Owen Kaser  
**arXiv:** [1603.06549](https://arxiv.org/abs/1603.06549)  
**Date:** 2016-03-21  
**Summary page:** https://www.summarizepaper.com/en/paper/1603.06549v4/

## Key points

- The paper discusses compressed bitmap indexes used in databases and search engines, focusing on the Roaring technique.
- Roaring is a hybrid compression technique that combines uncompressed bitmaps, packed arrays, and run-length encoding (RLE) compressed segments.
- It has been widely adopted by various production platforms due to its good performance.
- However, there are cases where run-length encoded bitmaps are smaller than the original Roaring bitmaps, especially when the data is sorted with long compressible runs.
- The authors propose a new implementation of Roaring that combines uncompressed bitmaps, packed arrays, and RLE compressed segments to address this issue.
- This new format achieves better compression compared to traditional RLE-based alternatives like WAH, Concise, and EWAH.
- The authors review the design choices and optimizations that contribute to the improved performance of their new implementation.
- Experiments were conducted on realistic datasets using a Linux server with an Intel i7-4770 processor and 32 GB of RAM to validate their results.
- The authors compare their new implementation with other bitmap formats and evaluate factors such as compression ratio and query performance.
- Overall, this paper provides valuable insights into bitmap compression techniques for handling unsorted data effectively while achieving superior performance compared to traditional RLE-based alternatives.

## Summary

The paper discusses compressed bitmap indexes used in databases and search engines, focusing on the Roaring technique. <br/>
Roaring is a hybrid compression technique that combines uncompressed bitmaps, packed arrays, and run-length encoding (RLE) compressed segments. It has been widely adopted by various production platforms due to its good performance. However, there are cases where run-length encoded bitmaps are smaller than the original Roaring bitmaps, especially when the data is sorted with long compressible runs. <br/>
To address this issue, the authors propose a new implementation of Roaring that combines uncompressed bitmaps, packed arrays, and RLE compressed segments. This new format achieves better compression compared to traditional RLE-based alternatives like WAH, Concise, and EWAH. The authors review the design choices and optimizations that contribute to the improved performance of their new implementation.<br/>
To validate their results, experiments were conducted on realistic datasets using a Linux server with an Intel i7-4770 processor and 32 GB of RAM. The authors compare their new implementation with other bitmap formats and evaluate factors such as compression ratio and query performance.<br/>
Overall, this paper provides valuable insights into bitmap compression techniques for handling unsorted data effectively while achieving superior performance compared to traditional RLE-based alternatives.