An operation can survive compression

Let a bitvector mark occupied hotel rooms:

room:  0 1 2 3 4 5 6 7 8 9
guest: 0 1 0 1 1 0 0 1 0 0

Two questions recur:

$$\operatorname{rank}_1(B,i)=\text{number of one-bits in }B[0..i),$$

$$\operatorname{select}_1(B,j)=\text{position of the }j\text{th one-bit}.$$

With zero-based occurrence indices, the example gives $\operatorname{rank}_1(B,7)=3$ and $\operatorname{select}_1(B,2)=4$.

Rank maps a position to an ordinal. Select maps an ordinal back to a position. Membership follows from two ranks:

$$B[i]=\operatorname{rank}_1(B,i+1)-\operatorname{rank}_1(B,i).$$

Predecessor follows from rank then select. These are not ornamental methods; they are a compact instruction set for navigating sets, trees, wavelet structures, and compressed text indexes.

Constant-time rank by remembering two scales

A full prefix-count array answers rank in constant time but stores about $m\log_2m$ bits for a bitvector of length $m$—larger than the data. Remember counts sparsely instead.

Choose superblocks of roughly $(\log_2m)^2$ bits and blocks of roughly $\tfrac12\log_2m$ bits.

• Each superblock stores the absolute number of ones before it.
• Each block stores the number of ones since its superblock began.
• The final short block is counted by a word popcount or a shared lookup table.

Then

$$\operatorname{rank}_1(B,i) =S[\operatorname{super}(i)] +C[\operatorname{block}(i)] +\operatorname{popcount}(\operatorname{tail}(i)).$$

There are $m/(\log m)^2$ superblocks, each using $O(\log m)$ bits, for $O(m/\log m)$ bits. There are $O(m/\log m)$ blocks, each using $O(\log\log m)$ bits, for $O(m\log\log m/\log m)$ bits. Both are $o(m)$.

The data and directory therefore occupy

$$m+o(m)$$

bits while rank uses a constant number of word operations in the word-RAM model. Constant-time select uses an analogous multiscale directory with special handling for dense and sparse regions; its proof is more involved, but its extra space is also lower order.

Split a monotone number into high and low evidence

Let

$$0\le x_0<x_1<\cdots<x_{n-1}<u.$$

Choose a low-bit width

$$\ell=\left\lceil\log_2(u/n)\right\rceil$$

when $u>n$, and $\ell=0$ otherwise. Split each value:

$$\operatorname{low}_i=x_i\bmod 2^\ell, \qquad \operatorname{high}_i=\left\lfloor x_i/2^\ell\right\rfloor.$$

Pack all lows in $n\ell$ bits. The highs are nondecreasing. Encode them in a unary bitvector $H$ by placing the $i$th one at

$$p_i=\operatorname{high}_i+i.$$

Zeros represent increases of the high quotient; ones represent sequence elements. This is the Elias–Fano split.

For $[3,5,8,14]$ in universe $u=16$, $n=4$ and $\ell=2$:

Thus $H=1010101$ through its final one, and the packed lows are $11,01,00,10$.

Select reconstructs any value

The $i$th one position satisfies

$$\operatorname{select}_1(H,i)=\operatorname{high}_i+i.$$

Therefore

$$\operatorname{high}_i=\operatorname{select}_1(H,i)-i$$

and

$$x_i=(\operatorname{high}_i\ll\ell)\mathbin{\vert}\operatorname{low}_i.$$

One select, one packed-field read, one subtraction, and one composition recover the $i$th value without decoding its predecessors.

High quotients also delimit buckets. To seek a target, locate its high bucket in $H$, then search only the corresponding contiguous lows. Practical quasi-succinct indexes add forward pointers or sampling so predecessor and nextGEQ do not scan long unary regions.

The exact space bound before the slogan

With $\ell=\lceil\log_2(u/n)\rceil$, the high quotient universe has at most

$$\left\lceil u/2^\ell\right\rceil\le n$$

values. The unary high bitvector therefore needs at most $2n+O(1)$ bits: at most $n$ zero positions and exactly $n$ one positions. The lows need $n\ell$ bits. The exact ceiling-aware construction bound is

$$n\left\lceil\log_2(u/n)\right\rceil+2n+O(1).$$

This is commonly summarized as about

$$n\log_2(u/n)+2n$$

bits, or $\log_2(u/n)+2$ bits per element, ignoring the at-most-one-bit rounding increase in each low field. The summary is useful; it is not an exact byte count for arbitrary $u/n$.

Compare it with Chapter 12's sparse-set floor:

$$\log_2\binom{u}{n} \approx n\log_2(u/n)+n\log_2e.$$

At power-of-two ratios, the idealized Elias–Fano excess is approximately

$$(2-\log_2e)n\approx0.557n$$

bits, before rank/select directories and alignment. With ceiling and finite effects, the excess is larger but still bounded by a small constant per value. That is the real claim: near the counting floor while retaining direct access.

Some presentations choose $\ell=\lfloor\log_2(u/n)\rfloor$. That saves low bits but permits a longer high bitvector. Both choices are valid; do not combine one choice's low cost with the other's high bound.

Partition when the local universe is different

A posting list can be globally sparse and locally clustered. One global $u/n$ ratio gives every element the same low width even when one region is dense and another contains a long jump.

Partitioned Elias–Fano divides the monotone sequence into chunks. For each chunk, subtract its base and encode its local range and count. Dynamic programming or a practical approximation chooses boundaries that trade:

• local Elias–Fano payload;
• partition headers and bases;
• boundary lookup cost;
• sequential and random query behavior.

A partition is worthwhile when reduced local universes repay their headers. Uniform data may gain nothing. Tiny partitions degenerate into metadata.

Succinct does not mean universally fast

Compare three representations:

Elias–Fano is static in this chapter. A single insertion can move packed lows, high bits, and directories, so a build-emitted index normally rebuilds or replaces a segment. Dynamic succinct structures exist, but their additional indirection and constants are a separate design, not a free mutation method.

For a tiny list, a flat array can win on bytes once headers and directories are counted, and on time because one cache line and a few comparisons beat a succinct traversal. For dense universes, an ordinary bitvector with rank/select may be simpler. For sequential scoring, a block codec may decode faster than repeated select. Measure the actual operation mix.

ELIAS-FANO-SELECT(HIGH-BITS, LOWS, WIDTH, INDEX)
Input:  unary HIGH-BITS with select support, packed LOWS, WIDTH, valid INDEX
Output: monotone value at INDEX

position ← SELECT-ONE(HIGH-BITS, INDEX)
high ← position - INDEX
low ← READ-PACKED(LOWS, INDEX, WIDTH)
return (high << WIDTH) OR low

The decoder validates $n$, $u$, width, high-bit length, low payload extent, one count, and monotonic reconstruction before publication. A rank/select directory is derived from the same immutable bitvector generation; a directory paired with different bits is not merely stale—it answers a different set.

What to test and measure

Prove the representation against a flat sorted oracle:

• select reconstructs every generated value;
• reconstructed values are strictly increasing and below $u$;
• rank/select membership agrees with the flat set;
• nextGEQ agrees on present, absent, boundary, and exhausted targets;
• serialized high bits and lows match pinned small examples;
• partitioned and unpartitioned forms answer identically;
• corrupted extents, counts, widths, and one totals are rejected.

Measure exact payload, directory, alignment, and header bytes separately. Benchmark sequential iteration, random select, predecessor, and intersection at tiny, cache-resident, and memory-resident sizes. The static-search layout lesson applies: batched throughput can hide memory latency that one interactive lookup must pay.

Lessons

• Rank counts marked positions before an index; select locates a marked ordinal.
• Multiscale directories make rank constant-time with lower-order extra bits.
• Elias–Fano stores low remainders directly and high quotients as unary gaps.
• The $i$th value is recovered from $\operatorname{select}_1(H,i)-i$ and its packed low field.
• With a ceiling low width, the exact construction uses at most $n\lceil\log_2(u/n)\rceil+2n+O(1)$ bits before directories.
• The familiar $n\log_2(u/n)+2n$ statement is an idealized summary, not an exact arbitrary-ratio byte count.
• Partitioning pays only when local clustering recovers more bits than its boundaries cost.
• Succinct describes space plus operations; it does not promise the fastest implementation for every workload.
• Static immutability is appropriate for shipped index generations and a poor fit for frequent point updates.

Practice

1. Build the superblock, block, and tail components for one rank query over a 32-bit example.
2. Elias–Fano encode $[2,3,9,15]$ with $u=16$. Write $\ell$, highs, lows, $H$, and reconstruct every value.
3. Prove the high bitvector has at most $2n+O(1)$ bits under the ceiling-width choice.
4. Find a non-power-of-two $u/n$ ratio where replacing the ceiling by the real logarithm understates actual low storage.
5. Construct a clustered list for which two partitions save payload, then add a header cost large enough to erase the win.
6. Design a crossover benchmark among flat integers, a gap codec, a bitvector, and Elias–Fano for sequential and random operations.

References

• Guy Jacobson. Succinct Static Data Structures. PhD thesis, Carnegie Mellon University, 1988.
• Sebastiano Vigna. “Quasi-Succinct Indices.” Proceedings of WSDM 2013, pp. 83–92.
• Giuseppe Ottaviano and Rossano Venturini. “Partitioned Elias–Fano Indexes.” Proceedings of SIGIR 2014, pp. 273–282.
• Gonzalo Navarro. Compact Data Structures: A Practical Approach. Cambridge University Press, 2016.