RRR bitvector
An RRR bitvector represents static bits by each block's number of ones and its pattern within that class, with auxiliary support for rank/select.
Encoding: A b-bit block with k ones has choose(b,k) possible patterns. A fixed-width class uses ceil(log2(b + 1)) bits, and its pattern index uses ceil(log2(choose(b,k))) bits. Query support adds samples and pointers. [1]
Bound: For length n and k ones, the fully indexable dictionary in Lemma 4.1 uses ceil(log2(choose(n,k))) + O(n log2(log2(n)) / log2(n)) bits. Constant-time rank/select assumes the paper's word-RAM model with Theta(log n)-bit words. This is an asymptotic bound, not a file-size formula. [2]
Example: At b = 15 and k = 7, there are 6435 patterns: 13 pattern bits plus 4 class bits give 17 bits before query support, versus 15 raw bits. At k = 0 or 15, no pattern bits are needed, but the class still costs 4 bits in this layout. Equal density need not give equal block budgets: two 30-bit examples total 8 versus 34 field bits. These are constructed counts, not library sizes. [3] [6]
Use: RRR can supply compressed routing bitmaps for sequence indexes. SDSL's rrr_vector is immutable after construction; block size and sampling affect space and access costs. Non-lexicographic offsets offer other decoding trade-offs. [5] Rank/select conventions remain explicit. [4]
Relations
Citations
- Navarro and Providel: Fast, Small, Simple Rank/Select on Bitmaps, SEA 2012, sections 1 and 3
- Raman, Raman and Rao: Succinct Indexable Dictionaries, arXiv:0705.0552v1 (2007), sections 1.1.3 and 4.1
- Hesela: exact fixed-width RRR block accounting, illustrative arithmetic only (CC0)
- SDSL tutorial: compressed immutable bitvectors and rrr_vector parameters
- Donges and Puglisi: Succinct Rank Dictionaries Revisited, SEA 2025, sections 2-4; DOI 10.4230/LIPIcs.SEA.2025.15
- Hesela: identical density, different RRR field budgets; generated synthetic examples and reproduction (CC0)
Sources & caveats
- RRR refers to the Raman-Raman-Rao construction; this record uses the full bitvector query contract, not the weaker indexable-dictionary rank operation that returns -1 for an absent key.
- The paper's o(k) indexable-dictionary redundancy must not be substituted for the full bitvector O(n log log n / log n) term when k is sparse.
- The downloadable calculation counts class and pattern fields only. It does not implement RRR queries, serialization, sampling or updates.
- The two 30-bit examples each contain 15 ones. At block size 15, clustered runs give classes 0 and 15; alternating bits give classes 7 and 8. Only class and pattern fields are counted. Headers, padding, sampling and lookup tables are excluded.
- A short code for one clustered input does not beat the worst-case bound for all 30-bit strings with 15 ones. The field code has variable total length across that class.
- SEA 2025 explores sparse lookup tables, weighted de Bruijn sequences and different offset orders. Its machine-specific access/rank experiments are not Hesela benchmarks or a general select-time guarantee.