Succinct data structures and Elias-Fano

When are near-entropy structures worth their constant factors, and why should you learn Elias-Fano?

The claim, stated precisely: Z + o(Z) bits, where Z is the information-theoretic minimum, with query support intact. The overhead is asymptotically negligible, not merely small. That distinction separates this class from "well compressed".

(Rank/select is the primitive and succinct structures are what you build from it; read this section as the second step of one subject.)

Succinct trees, with the number shown. The number of distinct ordinal trees (trees where children are ordered) with n nodes is the Catalan number C_n ≈ 4ⁿ/n^1.5. So log₂ C_n = 2n − O(log n): two bits per node is the floor. The LOUDS encoding (Level-Order Unary Degree Sequence) reaches 2n + o(n) bits, and navigates with rank/select. A pointer-based trie node costs 8 to 2,048 bytes. The ratio is three orders of magnitude, the difference between a term index that lives on disk and one that lives in RAM.

This is the same trie as in Lookup structures, whose fatal flaw was that every level is a dependent pointer chase. Succinct encoding does not fix the dependency. It fixes the size, which lets the whole structure sit in a tier where a dependent access costs 80 ns instead of 100 µs. The fix for a pointer-chasing structure was never to chase fewer pointers. It was to make the structure small enough that chasing is cheap. Lucene's FST (finite-state transducer) term index is this idea in production. SuRF is the LOUDS-based attempt to build a range filter, the gap identified in Probabilistic structures.

Elias-Fano is the one to actually learn, because monotone (non-decreasing) integer sequences are everywhere in data engineering: posting lists, offset arrays, sorted row IDs, sparse bitmaps. It is both optimal and simple. Take n increasing values from a universe of size u. Split each value into:

• low bits: the lowest log₂(u/n) bits, packed contiguously, costing n · log₂(u/n) bits in total;
• high bits: the remaining log₂n high bits, written in unary (the number h is written as h zeros then a one) into one bit vector of length about 2n, which is 2 bits per element.

Total: n · (2 + ⌈log₂(u/n)⌉) bits, within about half a bit per element of the information-theoretic bound for monotone sequences. Random access to element i is one select (on the high-bits vector) plus one packed read.

The honest assessment, because the theory oversells these structures. They are underused relative to their elegance, because of constant factors and implementation difficulty. A succinct structure that takes two cache misses per operation loses to a structure four times larger that takes one miss. Most of the time, the four-times-larger one is the right engineering call.

They win decisively in one situation, and it is a step function, not a gradient: when compactness moves the structure to a different tier of the hierarchy. Four times smaller and still on disk buys a 4 times I/O reduction. Four times smaller and now resident in RAM buys a factor of 1,000. This is the same argument as the Bloom filter's worth being the latency ratio of the boundary it guards, and the same argument as a B-tree's top levels being cached. We call it the Tier-boundary law:

It is labeled a candidate on purpose. It may be nothing more than the memory hierarchy's discrete levels restated, in which case it is a corollary of how storage tiers work and not a law of its own. It would earn the name if it appeared somewhere the hierarchy is not the mechanism, for example in coordination cost, schema size or organizational structure. Worth watching for; not worth asserting yet.