What Is Roaring Bitmap Compression?

Roaring bitmap compression is an advanced data structure designed to store and query large sets of 32-bit unsigned integers with exceptional speed and minimal memory overhead. Unlike traditional bitmaps or run-length encoding formats, Roaring bitmaps dynamically adapt their internal storage mechanism by partitioning data into chunks and storing them in array, bitset, or run containers based on local data density. This hybrid architecture allows systems to perform ultra-fast bitwise operations (AND, OR, XOR) directly on compressed data, making it a foundational indexing technology in modern analytical databases and search engines.

Architecture and Partitioning Strategy

Roaring bitmaps divide the 32-bit integer space \([0, 2^{32} - 1]\) into fixed-size chunks based on the binary representation of each number:

• Top 16 Bits (Chunk Key): The most significant 16 bits identify the specific chunk or partition (addressing up to 65,536 distinct ranges).
• Bottom 16 Bits (Container Value): The least significant 16 bits represent the actual value within that range \([0, 65,535]\) and are stored inside a dedicated container.

The top-level structure maintains an ordered dynamic array of 16-bit keys mapped to their corresponding containers. Because each container handles a maximum of \(2^{16} = 65,536\) distinct values, the system can select the optimal binary storage format per container independently.

The Three Container Types

Roaring bitmaps rely on three distinct container formats to optimize memory footprint and CPU cache efficiency according to the distribution of the integers.

1. Array Containers (Sparse Data)

When a partition contains fewer than 4,096 integers, it is stored as an Array Container. * Storage: An array of sorted 16-bit unsigned integers. * Memory Cost: Exactly 2 bytes per integer. For instance, storing 1,000 integers consumes 2,000 bytes. * Threshold Logic: If the number of elements in an array container reaches 4,096, its memory consumption reaches \(4,096 \times 2 = 8,192\) bytes (8 KB). At this threshold, it is automatically converted into a Bitset Container.

2. Bitset Containers (Dense Data)

When a partition contains 4,096 or more integers, it is stored as a Bitset Container. * Storage: A fixed-size bit array consisting of 1,024 64-bit words (\(1,024 \times 64 = 65,536\) bits = 8,192 bytes / 8 KB). * Memory Cost: Always fixed at 8 KB, regardless of whether it holds 4,096 or 65,536 integers. * Bitwise Representation: The \(n\)-th bit in the bitset is set to 1 if the integer \(n\) is present in the set, and 0 otherwise.

3. Run Containers (Contiguous Ranges)

A Run Container is used when data contains long, consecutive sequences of integers (runs), such as [10-500, 1000-2000]. * Storage: An array of 16-bit integer pairs representing (start_value, length). For example, the range \([10, 14]\) is encoded as the pair (10, 4). * Memory Cost: 4 bytes per run (2 bytes for the start value and 2 bytes for the run length). * Efficiency: Storing a contiguous block of 10,000 consecutive integers takes only 4 bytes in a Run Container, compared to 8 KB in a Bitset Container or 20 KB in an uncompressed array.

Dynamic Adaptation and Container Conversion

Roaring bitmaps evaluate data distributions both on write operations and through explicit optimization passes:

1. Threshold-Based Conversion: An Array Container converts to a Bitset Container as soon as cardinality exceeds 4,095 elements. If removals drop the cardinality back down to 4,096 or below, it converts back to an Array Container.
2. Explicit Run Optimization (runOptimize): Systems can analyze containers to determine if converting to Run Containers yields a smaller memory footprint. A Bitset Container with fewer than 2,048 runs or an Array Container with tightly clustered integers will be converted into a Run Container when it reduces total byte size.

Efficient Bitwise Set Operations

The primary advantage of Roaring bitmaps is fast set algebra (AND, OR, XOR, ANDNOT) executed directly at the container level:

• Bitset vs. Bitset: Operations execute via SIMD-accelerated 64-bit CPU instructions (e.g., bitwise AND/OR instructions directly over the 1,024 64-bit words).
• Array vs. Array: Set operations use two-pointer merge algorithms or binary search branching depending on size differentials.
• Array vs. Bitset: Elements from the array container are directly tested against or inserted into the 8 KB bitset using bit shifts and masks without converting the bitset.
• Run vs. Run / Bitset / Array: Handled via interval intersection and union algorithms or by scanning run intervals directly into bitmasks.

By combining the low memory usage of sparse arrays, the fixed-bound saturation of bitsets, and the compression power of run-length encoding, Roaring bitmaps deliver dense indexing performance that maximizes CPU cache locality and throughput in high-scale binary systems.