Roaring Bitmaps: Implementation of an Optimized Software Library

Daniel Lemire, Owen Kaser, Nathan Kurz, Luca Deri, Chris O'Hara +2 more
9/22/2017
cs.DB

Official code: RoaringBitmap/CRoaring (1,899 stars, last commit 2026-10-20). 1 more implementation below.

Abstract

Compressed bitmap indexes are used in systems such as Git or Oracle to accelerate queries. They represent sets and often support operations such as unions, intersections, differences, and symmetric differences. Several important systems such as Elasticsearch, Apache Spark, Netflix's Atlas, LinkedIn's Pinot, Metamarkets' Druid, Pilosa, Apache Hive, Apache Tez, Microsoft Visual Studio Team Services and Apache Kylin rely on a specific type of compressed bitmap index called Roaring. We present an optimized software library written in C implementing Roaring bitmaps: CRoaring. It benefits from several algorithms designed for the single-instruction-multiple-data (SIMD) instructions available on commodity processors. In particular, we present vectorized algorithms to compute the intersection, union, difference and symmetric difference between arrays. We benchmark the library against a wide range of competitive alternatives, identifying weaknesses and strengths in our software. Our work is available under a liberal open-source license.

View on arXivView PDF

Code Implementations(2)

RoaringBitmap/CRoaringOfficial100%

Roaring bitmaps in C (and C++), with SIMD (AVX2, AVX-512 and NEON) optimizations: used by Apache Doris, ClickHouse, Alibaba Tair, Redpanda, YDB and StarRocks

1,899338C, C++Dec 1, 20154 days agoNOASSERTION
armavx-512avx2bitsetbitset-library+6 more
lemire/EWAHBoolArrayOfficial100%

A compressed bitmap class in C++.

46085C++, CMakeNov 1, 20101 years agoNOASSERTION
bitmapbitsetcompressionewah

Similar Papers

Compressed bitmap indexes: beyond unions and intersections

86% match1 repo5682014

Consistently faster and smaller compressed bitmaps with Roaring

79% match1 repo3.9k2016

SIMD Compression and the Intersection of Sorted Integers

74% match1 repo4492014

Fast Exact Search in Hamming Space with Multi-Index Hashing

73% match1 repo2892013

Quicker ADC : Unlocking the hidden potential of Product Quantization with SIMD

72% match2 repos622018

Billion-scale similarity search with GPUs

71% match1 repo41.2k2017

Cite this paper

@article{lemire2017roaring,
  title  = {Roaring Bitmaps: Implementation of an Optimized Software Library},
  author = {Daniel Lemire and Owen Kaser and Nathan Kurz and Luca Deri and Chris O'Hara and François Saint-Jacques and Gregory Ssi-Yan-Kai},
  year   = {2017},
  eprint = {1709.07821},
  archivePrefix = {arXiv},
  url    = {https://arxiv.org/abs/1709.07821}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/1709.07821.svg)](https://codeofpaper.com/paper/1709.07821)

Discussion