Created: 2023-02-28T08:49:27-06:00
This card pertains to a resource available on the internet.
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.