# Roaring Bitmaps: Implementation of an Optimized Software Library

**Authors:** Daniel Lemire, Owen Kaser, Nathan Kurz, Luca Deri, Chris O'Hara, François Saint-Jacques, Gregory Ssi-Yan-Kai  
**arXiv:** [1709.07821](https://arxiv.org/abs/1709.07821)  
**Date:** 2017-09-22  
**Summary page:** https://www.summarizepaper.com/en/paper/1709.07821v1/

## Key points

- Authors discuss the use of compressed bitmap indexes in systems like Git and Oracle to enhance query performance
- Roaring bitmap indexes facilitate operations such as unions, intersections, differences, and symmetric differences
- CRoaring is an optimized software library written in C that implements Roaring bitmaps
- CRoaring leverages SIMD instructions for efficient computation of operations between arrays
- Ability to deactivate optimizations within CRoaring at compile time for fallback on portable C code
- CRoaring outperforms many alternatives in benchmarks even without optimizations, showcasing significant speed improvements in specific datasets

## Summary

, , , , 

In their paper titled "Roaring Bitmaps: Implementation of an Optimized Software Library," authors Daniel Lemire, Owen Kaser, Nathan Kurz, Luca Deri, Chris O'Hara, François Saint-Jacques, and Gregory Ssi-Yan-Kai discuss the use of compressed bitmap indexes in systems like Git and Oracle to enhance query performance. These indexes represent sets and facilitate operations such as unions, intersections, differences, and symmetric differences. The specific type of compressed bitmap index known as Roaring is utilized by various significant systems including Elasticsearch, Apache Spark, Netflix's Atlas, LinkedIn's Pivot, Metamarkets' Druid, Pilosa, Apache Hive, Apache Tez, Microsoft Visual Studio Team Services, and Apache Kylin. The authors introduce CRoaring - an optimized software library written in C that implements Roaring bitmaps. This library leverages algorithms designed for single-instruction-multiple-data (SIMD) instructions found on commodity processors. Particularly noteworthy are the vectorized algorithms within CRoaring that enable efficient computation of intersection, union, difference,
and symmetric difference between arrays. Through benchmarking against a range of competitive alternatives,the authors identify strengths and weaknesses in their software. Furthermore,the authors highlight the ability to deactivate optimizations within CRoaring at compile time to fallback on portable C code.Despite this deactivation of optimizations leading to reliance on advanced SIMD instructions by the compiler itself;CRoaring still outperforms many alternatives in benchmarks even without these optimizations. The study emphasizes the value of these optimizations by showcasing significant speed improvements in specific datasets while acknowledging smaller benefits or no impact in other scenarios. Overall,the research underscores the importance of optimizing already efficient code like CRoaring through targeted enhancements for specific cases. By focusing on improving performance in key areas while maintaining a strong baseline efficiency level even without optimizations enabled;CRoaring stands out as a robust solution for accelerating queries with compressed bitmap indexes.