Elias–Fano Maths: Succinct Monotone Indexes

Why is mathematics important in data compression and search? A modern index may store billions of increasing identifiers: document numbers containing a term, event times, graph neighbours, or positions of a symbol. The values can be large, but their order carries structure. Elias–Fano encoding exploits that structure by splitting each value into high and low parts, then representing the high parts with a bitvector.

The result is not ordinary file compression. It is a compact data structure designed to stay navigable. We can recover values in order and, with suitable support structures, perform operations such as select, rank, predecessor or skipping. This article develops the mechanism with a small worked sequence, checks the bit arithmetic, and explains where the method helps—and where it does not.

The problem is an ordered sequence

Imagine an inverted index for a collection of articles. For the term mathematics, the system stores the increasing document identifiers in which the term appears. A simple list might be 3, 5, 8, 12, 13 and 18. Fixed-width storage works, but it ignores two facts: the values never decrease, and there are only six values in a universe that ends at 18.

The same pattern appears elsewhere. A graph stores each vertex’s neighbours in sorted order. A log records increasing timestamps. A bitmap records positions of set bits. A column store keeps sorted integer keys. The application names differ, but the mathematical object is a monotone sequence.

Let the sequence contain (n) nondecreasing integers (x_0,\ldots,x_{n-1}), with each value in a universe from 0 up to some upper bound (U). Some presentations use a strict sequence and a universe size (u); formulas vary slightly with conventions. Correct implementation begins by fixing those conventions.

Why order is useful information

If six integers were arbitrary members of 0 through 18, every position would need enough bits to name any value. But an increasing sequence cannot take every possible arrangement. Once an early value is known, later values face constraints. Compression methods turn those restrictions into fewer stored bits.

Elias–Fano does this without encoding each gap as a separate variable-length word. It divides the binary representation at a carefully chosen point. Lower bits are stored directly; upper bits become a monotone quotient sequence represented by unary gaps in a bitvector.

The design is a fine lesson in mathematical modelling. Before choosing a codec, identify the object’s invariant. “These are integers” is less informative than “these are increasing integers drawn from a bounded universe.”

Static does not mean useless

Classical Elias–Fano is especially natural for a sequence built and then queried many times. Search indexes often create immutable segments and periodically merge them. That workflow can make a static representation practical even in an evolving system.

Dynamic variants and layered architectures exist, but updates are not free. A compact representation should be evaluated together with its lifecycle: how often data is appended, rebuilt, queried and discarded.

Information, gaps and monotonicity

One obvious compression strategy stores gaps: 3, then +2, +3, +4, +1 and +5. Small gaps may receive short codes. This can work well, but seeking to the thousandth value can require decoding many earlier gaps unless extra checkpoints are added.

Elias–Fano takes a different route. It keeps fixed-width low bits for direct access and puts monotone high bits into a bitvector that supports navigation. Sebastiano Vigna’s Quasi-Succinct Indices explains how this architecture can support practical inverted indexes. Peter Elias’s earlier 1974 JACM paper is a primary historical source for storage and retrieval of static files.

Choose the split width

A common choice is

(L=\lfloor\log_2(U/n)\rfloor), clipped at zero when necessary.

Here (U) should be interpreted consistently with the chosen implementation—often an upper bound or related universe parameter. The ratio (U/n) estimates the average spacing. The lower (L) bits capture detail within buckets of width (2^L); the remaining high bits identify the bucket.

For our sequence 3, 5, 8, 12, 13, 18, take (n=6) and upper bound (U=18). The ratio is 3. Since (\lfloor\log_2 3\rfloor=1), choose (L=1). Each value contributes one low bit, and its high part is the value shifted right by one bit, equivalently the floor after division by 2.

Why the split balances two costs

If (L) is large, low parts use many bits per value, while high quotients occupy a small range. If (L) is small, lows are cheap, but high quotients span more buckets and the unary bitvector grows. Choosing (L) near the logarithm of average spacing balances the terms.

This is not magic. It is an optimisation pattern: express total cost as competing pieces, then choose a parameter near the point where neither dominates. Similar reasoning appears in block sizes, cache tiling, sampling rates and numerical discretisation.

Strictly increasing versus nondecreasing

Some applications store duplicates. Classical formulas often assume monotonicity and can support nondecreasing values with appropriate encoding conventions. Others convert a nondecreasing sequence into a strictly increasing one by adding the index, then reverse that transformation during decoding.

Do not mix proofs or code from different conventions. State whether duplicates are allowed, what (U) means, and how the high bitvector is formed. A one-character difference in a formula can shift every decoded value.

Did You Know? Succinct has a technical flavour

In algorithms research, a succinct data structure aims to use space close to the information-theoretic amount needed for its object while still supporting useful operations. “Compressed” and “succinct” are related but not interchangeable marketing words. A format that produces a small file may require full decompression before queries; a succinct index is designed to remain operable in compact form.

The distinction illustrates why vocabulary matters. A precise term carries a performance and representation contract that can be tested.

Split every value into high and low bits

With (L=1), write each value (x_i) as

(x_i=(h_i\ll L)+\ell_i),

where (h_i=\lfloor x_i/2^L\rfloor) and ℓ(_i=x_i\bmod 2^L). The left shift multiplies the high part by (2^L). Because (L=1), the low part is simply the final binary bit.

For 3, binary 11, the high part is 1 and low part is 1. For 5, binary 101, high is 2 and low is 1. For 8, binary 1000, high is 4 and low is 0. For 12, high is 6 and low is 0. For 13, high is 6 and low is 1. For 18, high is 9 and low is 0.

So the high sequence is 1, 2, 4, 6, 6, 9 and the packed low bits are 1 1 0 0 1 0.

Recombination is exact

Check 13: high 6 shifted left one becomes 12, and low 1 restores 13. Check 18: high 9 becomes 18, and low 0 changes nothing. No approximation has occurred. Elias–Fano is lossless.

This decomposition is ordinary quotient and remainder arithmetic. For divisor (2^L), every non-negative integer has a unique quotient and remainder in 0 through (2^L-1). Binary operations make the calculation efficient, but the underlying theorem is the division algorithm.

Pack the low bits

Because every low field has the same width (L), the (i)-th low part starts at bit position (iL). Random access does not need to parse variable-length codes before it. Extract the field with a shift and mask.

When (L=0), there are no low bits: all information is carried by the high representation. A robust implementation handles this edge case explicitly rather than shifting by an unexpected width or allocating a meaningless array.

Keep bit order explicit

Diagrams often write the most significant bit on the left, while packed machine words may be addressed from the least significant bit. Both are fine if documented. A worked paper sequence should state its display order; code should specify how fields cross word boundaries.

Many bit-manipulation bugs are not advanced mathematics. They are failures to maintain a representation convention. Precision in notation prevents them.

A second mini-example

Suppose values are 2, 3, 7 and 8 with (L=1). Highs are 1, 1, 3, 4; lows are 0, 1, 1, 0. Recombining gives 2, 3, 7 and 8. The repeated high value shows why the high encoding must represent a nondecreasing sequence, not merely a set of distinct buckets.

This repetition is useful: values within the same bucket share a quotient, while low bits distinguish their positions inside it.

Encode the high parts in a bitvector

The high sequence 1, 2, 4, 6, 6, 9 is nondecreasing. Elias–Fano stores it by placing the (i)-th one at bit position (h_i+i), using zero-based indices. The added index makes positions strictly increasing even when adjacent high values are equal.

The one positions are therefore 1, 3, 6, 9, 10 and 14. A bitvector indexed from position 0 through 14 has ones at those locations and zeros elsewhere. Written left to right by increasing position, it is 010100100110001.

Different sources may display or terminate the vector differently, depending on universe and sentinel conventions. The reliable invariant is the position formula used by both encoder and decoder.

Why adding the index works

Because (h_{i+1}\ge h_i), we have (h_{i+1}+(i+1)>h_i+i). Thus every one position is strictly greater than the previous one. Equal high parts become adjacent ones. An increase of (g) in the high value creates (g-1) zeros between consecutive ones after accounting for the index step.

This is unary gap information. Instead of storing each high number in fixed width, the spacing of ones records how the quotient progresses.

Decode with select

Define select(_1(i)) as the position of the (i)-th one, under a clearly stated zero-based convention. Then

(h_i=\operatorname{select}_1(i)-i).

For the fourth value, (i=3), the fourth one is at position 9. Subtract 3 to obtain high part 6. Its fourth low field is 0, so the value is (6\times2+0=12).

For the fifth value, (i=4), the fifth one is at position 10. Subtract 4 to obtain the repeated high 6. Its low bit is 1, so the value is 13. Adjacent ones correctly represent two values in the same bucket.

Rank and select are small mathematical machines

Rank(_1(p)) counts ones up to a position; select(_1(i)) locates a numbered one. Efficient succinct bitvectors add auxiliary samples so these operations do not scan every bit. The precise time-space trade-off depends on the representation.

This layering is instructive. Elias–Fano relies on a bitvector abstraction, while the bitvector itself relies on smaller tables or summaries. Computer systems are often towers of contracts. Mathematical clarity at each layer keeps the tower dependable.

Did You Know? A zero is meaningful too

Zeros in the high bitvector mark progress through empty or partially empty high buckets. The number of zeros before a one helps reveal the high quotient. An apparently sparse pattern therefore carries two intertwined orders: sequence position through counted ones, and universe position through counted zeros.

That duality supports predecessor-style navigation. It is a vivid example of encoding two coordinates in a single monotone path.

Decode a complete worked example

Our stored parts are low bits 1, 1, 0, 0, 1, 0 and a high bitvector with one positions 1, 3, 6, 9, 10, 14. To recover value (i), find position (p_i) of the (i)-th one, calculate (h_i=p_i-i), read low field ℓ(_i), then compute ((h_i\ll1)+\ell_i).

For (i=0), (p_0=1), so high is 1. Low is 1. Value: 3. For (i=1), (p_1=3), high is 2, low is 1, value 5. For (i=2), (p_2=6), high is 4, low is 0, value 8.

For (i=3), position 9 minus index 3 gives high 6; low 0 gives 12. For (i=4), position 10 minus 4 gives 6; low 1 gives 13. For (i=5), position 14 minus 5 gives 9; low 0 gives 18. The original sequence is recovered exactly.

Check the monotonicity after decoding

A decoder used on untrusted or corrupted data may validate that recovered values do not decrease and remain inside the declared universe. The compact form alone does not provide magical integrity. Checksums, bounds validation and trusted metadata remain separate concerns.

Mathematical representation and systems safety complement each other. A proof assumes valid encoded objects; software must decide how to handle invalid bytes.

Locate a predecessor conceptually

Suppose we seek the greatest stored value not exceeding 14. Since (L=1), split 14 into high 7 and low 0. The high bitvector can help locate the range of sequence items whose high parts are below or equal to 7. Within the boundary bucket, compare low parts. The answer is 13.

An optimised predecessor algorithm depends on exact bitvector operations and conventions, so production code should follow a verified design rather than extrapolating from a paragraph. The conceptual value is clear: the high representation narrows the bucket, and fixed-width lows resolve detail.

Skip through a posting list

In an intersection query, one posting list may be at document 1,000 while another is at 1,500. A useful index should advance to the first value at least 1,500 without decoding every intervening gap. Quasi-succinct designs add navigation structures or exploit select operations to skip efficiently.

This is why compressed indexing differs from simply saving storage. Query operations shape the format. A smaller encoding that forces much more CPU or I/O may lose overall.

Test with round trips and reference lists

Generate monotone sequences, encode them, decode every position and compare with the originals. Include empty sequences if supported, one value, all-equal sequences if allowed, consecutive values, very sparse values, (L=0), word-boundary crossings and maximum universe values.

Then test navigation operations against simple array algorithms. A linear predecessor search is slow but transparent on small data. As with many advanced structures, the uncomplicated baseline is an excellent correctness oracle.

Space, queries and practical trade-offs

With (n) values, the low array uses exactly (nL) bits. The high bitvector length is roughly (n+(U\gg L)), subject to the chosen universe convention. Choosing (2^L) near (U/n) makes the quotient range roughly (n), so the high vector is roughly another (2n) bits. This leads to the familiar broad bound near (n(\log_2(U/n)+2)) bits for suitable assumptions.

Treat that expression as a model, not a byte-for-byte promise. Real implementations need headers, alignment, block metadata, select samples and object overhead. Small lists can be dominated by metadata. Partitioning a long list into blocks can improve local density at the cost of block descriptors.

Density determines the benefit

If (n) is close to the universe size, (U/n) is near 1 and (L) becomes zero. The high bitvector resembles a dense bitmap and can be efficient. If the sequence is sparse, larger low fields capture within-bucket positions while the high vector remains controlled.

The method adapts smoothly across densities, but another representation may win for a particular workload. Dense bitmaps, run-length encoding, variable-byte gaps or specialised integer codecs all deserve comparison.

Query support is not automatic

The mathematical encoding gives a path to access and navigation. Constant-time or fast rank/select usually requires auxiliary structures. The size and cache behaviour of those structures matter. A statement such as “supports select” is incomplete without the representation and computational model.

Similarly, a theoretical bit bound does not tell us throughput. Branching, memory locality, vector instructions and decompression batch size can dominate on modern hardware.

Partitioned Elias–Fano

A single global upper bound may poorly describe a list with uneven gaps. Partitioning divides the sequence into blocks and encodes each block with local parameters. Dense regions receive small low widths; sparse regions receive larger ones. The trade-off is metadata and the need to choose boundaries.

This illustrates a general technique: a global model is simple, while local models adapt to heterogeneity. Too many partitions overfit overhead; too few miss structure. Mathematics helps express the balance, and measurement selects a practical point.

Applications without hype

Elias–Fano-style representations are associated with inverted indexes, sorted identifiers, graph adjacency lists, positional data and related monotone sequences. Apache Lucene has documented an EliasFanoEncoder, which also points readers to the historical sources and Vigna’s design.

That does not imply every search engine or graph store uses the same layout. Engineering systems mix techniques based on update patterns, hardware and query needs. The mathematical mechanism is a tool, not a product guarantee.

Failure modes to watch

Using an inconsistent definition of (U) when choosing (L) and sizing the high vector.
Mixing zero-based and one-based select conventions.
Mishandling duplicate values or assuming strictness without validation.
Overflowing when shifting large high parts or computing universe ratios.
Forgetting metadata and support structures in space comparisons.
Comparing compressed size without comparing query latency and build cost.

Each failure is preventable when the representation contract is written before optimisation.

What this teaches about mathematics

Elias–Fano encoding turns school mathematics into a systems design. Division gives quotient and remainder. Logarithms choose a bit width. Binary place value splits and recombines numbers. Monotonicity permits a unary path. Counting operations recover coordinates.

The ideas are not valuable only because they save memory. They demonstrate how a property of data can be converted into an invariant that software exploits.

Logarithms answer a practical question

The expression (\lfloor\log_2(U/n)\rfloor) asks how many binary digits are appropriate for within-bucket detail at the average spacing scale. Logarithms are often introduced as inverses of powers; here they decide a physical layout.

Changing from base 2 would change the digit system, but computers make powers of two convenient for shifts and masks. The mathematical choice meets the machine model.

Two representations can preserve one object

The original integer sequence becomes low fields plus a high bitvector. Neither part alone is enough, but together they preserve every value. This teaches decomposition: find components with simpler structure, store each appropriately, and prove recombination.

The same habit appears in coordinates, scientific models, signal transforms and algebraic factorisation.

Compression depends on assumptions

If values are not monotone, the high one positions may not increase and the encoding fails. If the universe bound is wrong, sizing fails. If updates are frequent, rebuild costs may dominate. Mathematics does not say “this is best”; it says “under these conditions, these bounds and operations follow.”

Reading conditions as carefully as conclusions is a core benefit of learning mathematics.

Space and time are linked

Smaller data can fit better in caches and reduce I/O, potentially improving speed. Yet more compact representations may require extra decoding. There is no universal direction. A systems evaluation should measure total behaviour.

This prepares students to reject simplistic claims such as “compression always slows things down” or “fewer bits always means faster”. Both can be true or false depending on the workload.

From formula to a trustworthy format

Before an encoder becomes a file format, write a short specification. Define integer width, byte order, whether values are strict or nondecreasing, the meaning of the universe bound, the rule for choosing (L), bit order inside a word, select numbering and padding. Include one tiny test vector with expected low bits, high bits and decoded values.

Next, consider arithmetic safety. Computing (U/n) requires a policy when (n=0). Forming (h_i+i) can overflow a narrow integer even when each input value is valid. Shifts by the machine-word width are often invalid or surprising. A decoder should check sizes before allocating memory and reject positions outside the declared bitvector.

Version the format if conventions can change. A new rank/select sampling scheme may leave the core Elias–Fano bits unchanged but alter metadata. Readers should know which variant they are opening rather than guessing from length. If interoperability matters, publish the test vectors and round-trip property.

Finally, evaluate end to end. For an inverted index, measure intersections, skipping and cold-cache reads, not only sequential decoding. For a graph, measure neighbour scans and random vertex queries. Include build time and peak construction memory. Mathematical analysis predicts useful regimes; an operational profile shows whether the regime describes the actual service.

This progression—define, prove, validate, secure and measure—is reusable. It turns an elegant encoding into a dependable component without pretending that the theorem alone settles every engineering decision.

One final review asks whether monotonicity is genuine or manufactured. Sorting identifiers may destroy an application’s original order, while adding indexes to handle duplicates changes the universe. A good design records the transformation and proves that decoding reverses it. It also keeps a plain representation available in tests so every compressed operation has an unambiguous reference. Compactness is valuable only when meaning survives intact.

Learning path for students

Begin with binary representations of small integers. Practise quotient and remainder by powers of two. Then take an increasing sequence, choose (L), list all highs and lows, and recombine them before attempting the unary high vector.

Next, place ones at (h_i+i). Number positions and ones explicitly. Decode with select and verify every value. Only after this paper exercise should code pack bits into machine words.

A four-stage project

Stage 1: arithmetic model. Split and recombine integers for several values of (L), including zero.
Stage 2: bitvector model. Encode high sequences and decode them using a simple linear select operation.
Stage 3: packed implementation. Store fixed-width lows across word boundaries and add tests.
Stage 4: evaluation. Compare bits per value and query time with a plain integer array and a gap codec.

The simple linear select in Stage 2 is intentionally slow. It isolates correctness. Optimised select samples can be added after the representation works.

Design experiments, not demonstrations

Use sequences with uniform gaps, clustered gaps, long empty regions and dense runs. Predict which representation will win. Measure encoded bytes including metadata, construction time, sequential decoding and random access.

If a result contradicts the prediction, investigate cache behaviour, language overhead and tiny-input effects. Unexpected evidence is a learning opportunity, not a failed experiment.

Explain the formula in words

Ask the student to narrate (h_i=\operatorname{select}_1(i)-i). A good explanation is: the one’s position counts both earlier values and high-bucket progress; subtracting the number of earlier values leaves the high quotient.

Being able to translate symbols into a mechanism is stronger than copying code. It also exposes indexing-convention mistakes quickly.

Extension questions

How does the chosen (L) change if the universe doubles while (n) stays fixed? What if (n) doubles? Why do equal highs produce adjacent ones? How could blocks adapt to uneven density? Which errors appear when addition or shifts overflow?

These questions connect algebraic reasoning, discrete structures and software reliability.

Guidance for parents and educators

Begin with something tangible: sorted page numbers in a book index or increasing bus arrival timestamps. Ask what is redundant about writing every number in full. Let the learner propose gaps before showing the high/low split.

Use coloured cards for bit positions. One colour can represent low fields; another can mark ones in the high vector. Moving between 13, its quotient 6, its low bit 1 and one position 10 makes the abstraction visible.

Reward precise conventions

If a student asks whether positions start at zero or one, that is progress. Many advanced-looking bugs come from unstated conventions. Encourage them to write the convention at the top of the page and test the first and last values.

Likewise, ask what (U) means in their implementation. Is it the maximum value, maximum plus one, or a known upper bound? The right answer is less important than consistency with the formulas and allocated storage.

Separate proof from benchmark

The space analysis explains why the representation can approach a useful bound. It does not prove that a particular library is fastest. Have learners make two columns: statements justified algebraically and statements that require measurement.

This is healthy reasoning across subjects. Evidence type should match the claim.

Keep pathways open

Succinct data structures appear in information retrieval, databases, graphs, bioinformatics and systems research. Those examples can motivate study, but do not turn them into promises about admissions or employment. The transferable value lies in decomposition, representation, proof and evaluation.

For an approachable everyday comparison of proportional reasoning, read Why Mathematics? | Comparing Percentages Fairly. To see another bit-level spatial representation, continue with Why Mathematics? | Z-Order Curves, Bit Interleaving, Spatial Locality and Range Queries.

Frequently asked questions

A compact classroom investigation

Create three monotone sequences with sixteen values: one dense, one evenly spaced and one containing a dense cluster followed by a long gap. For each sequence, compute (U/n), choose (L), split every value, and count the low bits and high-vector bits. Then repeat with nearby choices of (L).

Students should distinguish the mathematical payload from practical overhead. First compare only the two bit arrays. Then add a realistic header, universe bound and select samples. A parameter that looks best in the idealised count may not minimise total bytes for a tiny list. Finally, decode every value and run predecessor checks against the plain sequence. This investigation joins algebra, representation and honest measurement.

Is Elias–Fano ordinary compression?

It is a compact representation specialised for monotone integer sequences and designed to support navigation. Unlike a general-purpose compressed file, it can expose access and search operations without fully expanding the list, given suitable bitvector support.

Why must the sequence be monotone?

The high quotients must be nondecreasing so the one positions (h_i+i) are strictly increasing. Arbitrary ordering breaks that structure. You could sort data only if the application does not need the original order.

What does the parameter L do?

It sets the number of low bits stored per value. A common choice near (\lfloor\log_2(U/n)\rfloor) balances low-array size against high-bitvector length. Exact conventions should follow the implementation and source.

Are duplicates allowed?

They can be supported under a nondecreasing convention, because adding the index still creates distinct one positions. Some implementations assume strictly increasing values or transform duplicates. Check and state the contract.

What are rank and select?

Rank counts marked bits up to a position; select locates the position of a numbered marked bit. They are fundamental navigation operations for succinct bitvectors and many compact data structures.

Does Elias–Fano always use less memory?

No. Headers, support structures and small-list overhead can outweigh savings. Other codecs may suit different densities or query patterns. Compare complete representations on realistic data.

Can I insert values into the middle cheaply?

Not in the simplest static packed representation. Systems may buffer updates, use dynamic variants or rebuild immutable segments. Update strategy is part of the design choice.

What should I verify first in code?

Round-trip every value, especially (L=0), repeated highs, boundary values and fields crossing machine words. Then compare rank, select and predecessor results against simple reference algorithms.

Useful next reading

Read Peter Elias’s Efficient Storage and Retrieval by Content and Address of Static Files for historical foundations.
Read Sebastiano Vigna’s Quasi-Succinct Indices for a modern index architecture and careful analysis.
Inspect the documented Apache Lucene EliasFanoEncoder as an implementation-oriented reference, while noting its API status and version.
Compare the bit-level locality story in Z-Order Curves and the sequence-alignment story in Dynamic Time Warping.

Elias–Fano encoding is a compact reminder that order is data. By splitting values at the scale suggested by density, it transforms an increasing sequence into fixed-width details and a navigable unary path. The method rewards exactly the habits mathematics education should cultivate: name the invariant, derive the representation, test the boundary cases and measure the complete system.

Why Mathematics? | Elias–Fano Encoding, Monotone Sequences, Bitvectors and Succinct Indexes