roaring-bitmap · shipping · also Roaring bitmaps, Roaring compressed bitmap

Roaring bitmap

Roaring is an exact integer-set representation that partitions identifiers into containers stored as sorted arrays, bitsets or runs.

Layout: Standard 32-bit Roaring groups unsigned identifiers by their high 16 bits. Each container represents the low 16 bits within one 65,536-value interval. Empty containers are omitted. [1]

Boundary: For a non-run container, cardinality at most 4096 selects an array; larger cardinality selects an 8192-byte bitset. The array payload uses two bytes per value, so both payload sizes equal 8192 bytes at 4096. This threshold does not prohibit a run container above or below it. [1]

Clustering: A serialized run container with r runs uses 2 + 4r bytes. Thus 4096 consecutive values need a six-byte run payload, while 4096 separated singletons need 16,386 bytes if encoded as runs. These are container payloads, excluding stream headers, offsets and in-memory allocation. [1] [4]

Operations: Container types shape intersection, union and difference algorithms. Runs help clustered identifiers, while scattered sets may favor arrays or bitsets. Run optimization can trade conversion work against space; smaller storage does not imply faster queries for every workload. [2] [3]

Relations

related
Bitmap index, Lossless compression, Elias-Fano encoding

Citations

  1. RoaringFormatSpec, pinned revision 188a7c75, standard 32-bit layout and container storage (accessed 2026-11-17)
  2. Lemire, Ssi-Yan-Kai and Kaser, Consistently faster and smaller compressed bitmaps with Roaring, arXiv:1603.06549v4 (accessed 2026-11-17)
  3. Lemire et al., Roaring Bitmaps: Implementation of an Optimized Software Library, arXiv:1709.07821v6 (accessed 2026-11-17)
  4. Hesela: executable single-container payload accounting and exhaustive small-set tests (CC0) (accessed 2026-11-17)
Sources & caveats
  • The worked examples are exact format arithmetic for synthetic sets, not CRoaring measurements or serialized whole-file sizes. [4]
  • The standard 32-bit format is scoped separately from 64-bit extensions; implementations may have different in-memory layouts. [1]
  • The 2016 journal article is consulted through its 2018 arXiv v4 revision; the implementation paper through its 2022 v6 revision. No performance result is reproduced.

JSON: /data/terms/roaring-bitmap.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Roaring bitmap. Hesela. 2026-11-17. https://hesela.dev/terms/roaring-bitmap/