Roaring Bitmap

Roaring bitmap is a hybrid compressed bitmap data structure within computation and algorithms designed to represent and manipulate sets of 32-bit or 64-bit unsigned integers with high memory efficiency and hardware-accelerated Single Instruction, Multiple Data (SIMD) throughput. Introduced by Samy Chambi, Daniel Lemire, Owen Kaser, and Robert Godin in 2016 (and extended with run-length containers by Lemire, Ssi-Yan-Kai, and Kaser in 2016), Roaring bitmaps overcome the cpu-bound decoding bottlenecks of traditional word-aligned run-length compressed bitmaps such as Word-Aligned Hybrid (WAH), Enhanced Word-Aligned Hybrid (EWAH), and Concise.

Instead of encoding an entire universe of 2³² integers as a single monolithic bitstream of variable-length run words, a Roaring bitmap partitions the 32-bit integer space [0, 2³² − 1] into at most 2¹⁶ = 65,536 contiguous chunks of 2¹⁶ = 65,536 integers each, indexed by the most significant 16 bits of each integer. Within each chunk, the least significant 16 bits of the present integers are stored in one of three specialized containers chosen dynamically according to local density and contiguity: a packed sorted array of 16-bit integers (for sparse chunks with ≤ 4,096 elements), a fixed 8-kilobyte uncompressed bitset (for dense chunks with > 4,096 elements), or a run-length encoded (RLE) interval array (for contiguous runs). Today, Roaring bitmaps serve as the standard inverted-index and columnar bitmap engine in Apache Lucene, Elasticsearch, Apache Spark, ClickHouse, Apache Druid, and DuckDB.

High-16 / Low-16 Bit Decomposition

Every 32-bit unsigned integer x ∈ [0, 2³² − 1] is split by bit-shifting into two 16-bit unsigned words:

• Chunk Key (Most Significant 16 Bits): k = ⌊x / 2¹⁶⌋ = x >> 16 ∈ [0, 65,535].
• Container Offset (Least Significant 16 Bits): v = x mod 2¹⁶ = x & 0xFFFF ∈ [0, 65,535].

A top-level index directory maintains a sorted array of active 16-bit chunk keys keys[0 .. m − 1] alongside a parallel array of pointers to their corresponding containers containers[0 .. m − 1]. Because empty chunks are omitted from the top-level directory, sparse sets spanning a large integer universe allocate zero memory for empty 65,536-integer regions.

The Three Container Formats and the 4,096-Element Threshold

Within each active 16-bit chunk, the set of 16-bit offsets S_k ⊆ {0, 1, …, 65,535} of cardinality c = |S_k| is stored using whichever of three container representations minimizes memory footprint while supporting random access:

1. Array Container (Sparse: c ≤ 4,096): Stores the c 16-bit unsigned integers (16-bit unsigned integer) in a contiguous sorted dynamic array, plus a 16-bit cardinality counter. Each element consumes 2 bytes (16 bits), so the container size grows linearly as 2c bytes.
2. Bitmap Container (Dense: c > 4,096): Stores a fixed-size uncompressed bit array of 2¹⁶ = 65,536 bits, packed into 1,024 64-bit machine words (1,024 64-bit words), occupying 8,192 bytes (8 KB) regardless of how many bits are set, alongside a precomputed cardinality counter.
3. Run Container (Contiguous Runs): Stores a sorted array of (start, length - 1) pairs of 16-bit integers ((16-bit start, 16-bit length)), where each 4-byte pair represents a contiguous closed interval [start, start + length - 1] of set bits. If a chunk contains r contiguous runs, the run container occupies 4r bytes.

Why is the crossover threshold between an Array Container and a Bitmap Container fixed at c = 4,096? At c = 4,096 elements, a sorted array of 16-bit integers occupies 4,096 × 2 bytes = 8,192 bytes (8 KB)—the identical byte size of a 65,536-bit uncompressed Bitmap Container. Below 4,096 elements, the sorted array uses strictly less than 8 KB; above 4,096 elements, the fixed 8 KB bitset uses less memory than a sorted array and fits completely inside the 32 KB L1 data cache of a modern CPU core. When inserting the 4,097-th element into an Array Container, it converts in place into a Bitmap Container; when deleting down to 4,096 elements, it converts back into an Array Container.

Pairwise Intersection, Union, and Difference Dispatch

To compute the intersection (A ∩ B), union (A ∪ B), or symmetric difference (A ⊕ B) of two Roaring bitmaps, the top-level algorithm walks the two sorted 16-bit chunk-key arrays A.keys and B.keys via a two-pointer merge (or skewed galloping binary search when one bitmap has far fewer chunks than the other). Whenever both bitmaps contain a chunk with the same 16-bit key k, a specialized pairwise kernel is dispatched based on the types of the two containers:

• Bitmap ∩ Bitmap: Executes 1,024 64-bit bitwise AND operations (or 128 512-bit AVX-512 vpandq instructions) across the two 8 KB arrays while accumulating the new cardinality via hardware population-count instructions (POPCNT / vpopcntq) in roughly 150–300 CPU clock cycles. If the resulting cardinality is > 4,096, the result remains a Bitmap Container; if ≤ 4,096, the set bits are extracted into an Array Container using trailing-zero instructions (TZCNT / ctzll).
• Array ∩ Bitmap: Iterates through the c ≤ 4,096 integers in the sparse Array Container and tests each integer against the Bitmap Container in O(1) time per element ((bitmap[v >> 6] >> (v & 63)) & 1), outputting matching integers directly into a result Array Container in O(c) branchless operations—never scanning the 8 KB bitmap.
• Array ∩ Array: When the two arrays have similar lengths, executes a SIMD-accelerated two-pointer merge comparing 8 or 16 16-bit unsigned integer elements per vector register; when one array is much smaller than the other (c₁ · 64 < c₂), executes a skewed galloping (doubling-stride) search in O(c₁ log(c₂ / c₁)) time.

Comparison With WAH, EWAH, and Probabilistic Filters

In classical Word-Aligned Hybrid (WAH) and EWAH bitmaps, run-length fill words (runs of all-0 or all-1 31-bit or 63-bit words) are interleaved sequentially with literal bit words. Because run lengths vary dynamically, WAH and EWAH cannot perform O(1) random access to test whether integer x is set without scanning from the beginning of the compressed stream, and intersecting a 3-element sparse set with a 10-million-element dense set still requires decoding the dense stream. By isolating every 65,536-integer block into an independently addressable container and handling Array ∩ Bitmap in O(c_sparse) probes, Roaring bitmaps achieve 10× to 100× speedups over WAH/EWAH on skewed analytical queries while complementing probabilistic structures such as Bloom filters whenever zero false positives and lossless set cardinality are required.

Extending Roaring to 64-Bit Integers

For applications indexing 64-bit document identifiers, row offsets, or genomic coordinates (Roaring64Map), the high 32 bits of each 64-bit integer (x >> 32) are indexed using a cache-conscious B-tree or adaptive radix tree (ART), where each leaf points to a standard 32-bit Roaring bitmap storing the low 32 bits (x & 0xFFFFFFFF).

Columnar OLAP Databases, Inverted Search Indexes, and Genomics

In full-text search engines (Apache Lucene, Elasticsearch, Tantivy), posting lists of document IDs that exceed a frequency threshold are cached as Roaring bitmaps so multi-term Boolean filter clauses (status:active AND region:US AND NOT archived:true) execute as L1-cache-resident container operations. In columnar OLAP databases (ClickHouse, Apache Druid, Pinot, StarRocks), Roaring bitmaps power lossless distinct-count (COUNT(DISTINCT user)) sketches and bitmap indexes for sub-second funnel and cohort retention queries, while in bioinformatics, colored de Bruijn graph indices (such as Bifrost) use Roaring bitmaps to map each genomic k-mer to the compressed set of reference genomes in which it occurs.

Why does Roaring use 16-bit chunks (65,536 integers) instead of 8-bit or 24-bit chunks?

Choosing 2¹⁶ = 65,536 integers per chunk is an architectural sweet spot for modern CPU caches and integer widths: first, intra-chunk offsets fit cleanly in a native 16-bit unsigned integer (16-bit unsigned integer, 2 bytes per element in Array Containers); second, an uncompressed bitset of 2¹⁶ bits occupies 8,192 bytes (8 KB), so two Bitmap Containers plus an output buffer (24 KB total) fit comfortably inside a single 32 KB or 48 KB L1 data cache during SIMD pairwise intersections.

How does a Roaring bitmap extract set integers from a Bitmap Container without testing all 65,536 bits?

Instead of looping over all 65,536 individual bit positions, Roaring iterates over the 1,024 64-bit words w = bitmap[k]. While w != 0, it extracts the index of the lowest set bit in a single CPU cycle using the hardware trailing-zero count instruction (hardware count-trailing-zeros on w / TZCNT), emits 64 * k + tz, and clears the lowest set bit via the bit-manipulation idiom w &= (w - 1) (BLSR). Consequently, iterating over all set bits in a Bitmap Container with c elements takes O(1024 + c) instructions rather than 65,536 loop iterations.

When should runOptimize() be called to convert Array or Bitmap Containers into Run Containers?

By default, dynamic single-element insertions create Array and Bitmap Containers to keep insertion latency at O(1) or O(log c). Once a bitmap is constructed (or before serializing it to disk or network storage), calling runOptimize() scans each container in O(1) time (counting bit transitions w ^ (w << 1) via POPCNT in Bitmap Containers) and converts any container whose run-encoded size 4r is smaller than both 2c and 8,192 bytes into a Run Container.

1. Chambi, S., Lemire, D., Kaser, O., & Godin, R. (2016). "Better bitmap performance with Roaring bitmaps." Software: Practice and Experience, 46(5), 709–719. https://doi.org/10.1002/spe.2325
2. Lemire, D., Ssi-Yan-Kai, G., & Kaser, O. (2016). "Consistently faster and smaller compressed bitmaps with Roaring." Software: Practice and Experience, 46(11), 1547–1569. https://doi.org/10.1002/spe.2402
3. Lemire, D., Kaser, O., Kurz, N., Deri, L., O'Hara, C., Saint-Jacques, F., & Ssi-Yan-Kai, G. (2018). "Roaring bitmaps: Implementation of an optimized software library." Software: Practice and Experience, 48(4), 867–895. https://doi.org/10.1002/spe.2560
4. Wu, K., Otoo, E. J., & Shoshani, A. (2006). "Optimizing bitmap indices with efficient compression." ACM Transactions on Database Systems, 31(1), 1–38. https://doi.org/10.1145/1132863.1132864