Roaring Array-Bitmap Container Threshold
See a bitmap switch representation as a set crosses a container threshold or a high-word boundary.
Free theory articleSee a bitmap switch representation as a set crosses a container threshold or a high-word boundary.
Concept & interpretation
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).
experiment
You can test how the container dynamically changes its representation based on cardinality thresholds in the Roaring Array-Bitmap Container Threshold module.
- 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.
- Set the Prefix count to 4097. Notice the representation switches to a Bitmap container, keeping the payload exactly 8192 bytes, which optimizes performance.
- Adjust Second offset and Second count to introduce numbers crossing the 65536 threshold to see the creation of new containers for different high words.
A primary reference detailing the internals of the Roaring Bitmap structure.
A primary reference detailing the internals of the Roaring Bitmap structure.
A primary reference detailing the internals of the Roaring Bitmap structure.