• Whitepaper on arXiv

Overview

Buckets can be stored as run length encoding on runs of hot and cold bits in the bucket.

Though we refer to a Roaring bitmap as a bitmap, it is a hybrid data structure, combining uncompressed bitmaps with sorted arrays.

Bitmap container: just stores the machine word(s) directly.

Array container: a sorted array of bits that are hot in a given range.

Range container: a large run of bits is encoded as two 16-bit integers: starting bit and length minus one of all hot bits. Range containers are only in the "Roaring+Run" algorithm.

The value of implementations is the heuristics used to determine what the best container type is for given spans of data.