Rank & Select

Last week: Models of computation Link to heading

• Big-O notation
• Word RAM model
  • Applications & limitations

Today Link to heading

• Bit vectors
  • storing bits
• Rank
  • counting 1-bits
• Select
  • finding 1-bits
• Engineering Rank
  • making it fast
• Elias-Fano coding
  • storing integers efficiently

Bit vectors Link to heading

Implemented using e.g. Vec<u64>.

1
2
3
4
5

fn get(data: &Vec<u64>, i: usize) -> bool {
    let word = data[i / 64];         // compiled to >> 6
    let idx = i % 64;                // compiled to & 0b0011_1111
    return ((word >> idx) & 1) > 0;
}

Little Endian: the low-order bits are first in memory.

\[ \newcommand{\rank}{\mathsf{rank}} \newcommand{\select}{\mathsf{select}} \]

Binary Rank & Select Link to heading

Also: \(\rank_0\) and \(\select_0\) for counting/finding 0-bits.

Binary Rank & Select: Goal Link to heading

Rank: first steps Link to heading

Rank: Binary search Link to heading

Rank: Checkpoints Link to heading

• Adjacent checkpoints \(R_k\) are similar!

Rank: A succinct version (Jacobson 1988) Link to heading

Rank: Emulating popcount Link to heading

• Originally, constant time \(w\)-bit popcount was not assumed.

• Instead, we can take \(s = (\log_2 n)/2\), and pre-compute popcounts for all \(2^s\) masks:

  • \(2^s = \sqrt{n}\) patterns
  • \(s\) offsets per pattern
  • \(\log_2 s\) bits per count

  \[2^s \cdot s \cdot \log_2 s = O(\sqrt n \cdot \log_2 n \cdot \log_2\log_2 n) = o(n).\]

Engineering Rank: minimizing space usage Link to heading

In practice, we don’t need succinct. Compact with small constant overhead is enough. See QuadRank slides.

• \(s=512\): Store a 64-bit checkpoint every 512-bits of data:
  • \(64/512 = 12.5\%\) space overhead;
  • pop-counting 512 bits is sufficiently fast.

• Smaller, \(s’=2^{16}\): 16-bit checkpoints, and \(s’=2^{16}\)-bit super blocks storing 64-bit checkpoints. (Kurpicz 2022)
  • \(16/512 + 64/2^{16} = 3.2\%\) overhead.

• Faster count: checkpoints to the middle of each block: (Gottlieb and Reinert 2025)
  • popcount only 256 bits.

• Fewer cache misses: store checkpoints inside each block: (Laws et al. 2024)
  • 1 instead of 2 cache misses
  • \(16/(512-16) + 64/2^{16} = 3.3\%\) overhead.

• Simple & fast classic: Rank 9 (Vigna 2008)
  • 64-bit blocks with 9-bit checkpoints; 7 of them make a u64.

Select Link to heading

Assume we have \(k\) 1-bits.

• Compute all answers on-demand: \(O(n/\log n)\) queries.
• Store all answers: \(O(k)\) words.
  • Sufficient if \(k = o(n / \log n)\).

1

(1 << i).deposit_bits(word).trailing_zeros()

Succinct Select (Clark and Munro 1996) Link to heading

Select in practice: Darray Link to heading

• Super blocks containing \(b = 2^{10}\) ones.
• Sparse if length \(\geq 2^{16}\)
  • Use \(2^6=64\) bits to encode each position; \(64\cdot 2^{10} = 2^{16}\) bits

• Dense blocks (len \(<2^{16}\)):
  • Store position of every \(2^5=32\)’nd 1, relative to start (10 bits each).
  • Linear scan (\(<2^{16}\)) from there to find the exact answer.
  • The last sparse/dense split from Clark’s select (previous slide) is skipped.

Further reading Link to heading

• QuadRank slides and paper (Groot Koerkamp 2026)
• Ben Langmead’s teaching material on bitvectors, rank, and select.
  • With YouTube videos.

Next: Elias-Fano coding Link to heading

Bibliography Link to heading

References Link to heading

Possible exam questions Link to heading

• What does a rank query return? And select? How do they relate to each other?
• What is the main technique used to obtain a succinct rank data structure? And for select?
• Name a few ways in which practical rank methods differ from the Jacobson’s theoretical version.
• How does Darray differ from Clark’s select?
• Which modern CPU instructions can be used for rank and/or select? What older techniques do they replace?
• For both rank and select, why does a single layer of blocks not suffice to obtain \(o(n)\) space and \(O(1)\) query time?

Blackboard: Bit vector & Rank Link to heading

Blackboard: Select & Darray Link to heading