Roaring Array-Bitmap Container Threshold

The Roaring Bitmap is a highly optimized set data structure that represents a set of 32-bit integers by partitioning them into high-word keys and low-word values. Each high-word (the top 16 bits) maps to a container that holds the corresponding low-words (the bottom 16 bits). A container can either be an array container (for sparse regions) or a bitmap container (for dense regions).

worked-example

Let's consider a set with a prefix of 4096 elements starting from 0, and we add an additional element that falls into a different high-word boundary.

Set X = {0, 1, 2, ..., 4095} (Prefix count = 4096)
Set Y = {} (Second count = 0)
Set operation: Union

High word 0: {0, 1, ..., 4095}
Cardinality of High word 0 = 4096.

Threshold: 4096.
Since cardinality <= 4096, High word 0 uses an Array Container.
Payload bytes = 4096 * 2 = 8192 bytes.
Container Layout: 0:Array:4096:8192

experiment

You can test how the container dynamically changes its representation based on cardinality thresholds in the Roaring Array-Bitmap Container Threshold module.

A primary reference detailing the internals of the Roaring Bitmap structure.

Set the Prefix count to 4096. Observe that the container for high-word 0 is an Array container because the cardinality is at the threshold of 4096.

A primary reference detailing the internals of the Roaring Bitmap structure.

Set the Prefix count to 4097. Notice the representation switches to a Bitmap container, keeping the payload exactly 8192 bytes, which optimizes performance.

A primary reference detailing the internals of the Roaring Bitmap structure.

Adjust Second offset and Second count to introduce numbers crossing the 65536 threshold to see the creation of new containers for different high words.

limitations

This exploration focuses strictly on the Array-versus-Bitmap split and the container memory threshold. Real-world implementations of Roaring Bitmaps also employ run containers for continuous sequences to further compress data, which are omitted here to highlight the array-to-bitmap crossover explicitly.

references

A primary reference detailing the internals of the Roaring Bitmap structure.

Consistently faster and smaller compressed bitmaps with Roaring- The original paper detailing the design, thresholds, and performance of Roaring Bitmaps.

Roaring Array-Bitmap Container Threshold