How to Learn Elias–Fano Encoding: Monotone Integer Sequences, High/Low Bit Splitting, Unary Gaps, Select and Succinct Search

Wait, What?

A sorted list of huge integers can be stored close to its information-theoretic minimum and still be navigated without fully decompressing it.

Most beginners meet compression as a trade: use fewer bits, then pay to decode everything before searching. Elias–Fano is more interesting. For monotone integer sequences, it splits every value into high and low parts so that the low bits remain directly packed while the high parts become a sparse unary-style bitvector.

The result is not merely a file format. It is a data-structure idea: compression and navigation can coexist.

For a beginner, Elias–Fano is a story about splitting binary numbers. At intermediate level, the key move is storing the high parts as one-bits whose positions encode both value and rank. At advanced level, you reason about select operations, space bounds and successor-style navigation. At professional level, the questions become density, bit packing, indexing overhead, vectorized decoding, upper-bound choice, interoperability and whether a plain bitset, delta code or other compressed representation is actually better for the workload.

Quick Answer

Learn Elias–Fano in this order: sorted integer sequences → binary high/low splitting → choose L from the universe-to-count ratio → pack all low L-bit suffixes → encode each high part by placing a 1 at position high[i]+i → recover high[i] with select1(i)-i → reconstruct values → understand the space bound → add rank/select indexing for navigation → compare with gaps, bitsets and variable-byte codes → test duplicates, empty inputs and extreme universes → benchmark bytes and query speed on real distributions.

1. The input contract is monotonicity

Suppose we have a nondecreasing sequence:

0 ≤ x[0] ≤ x[1] ≤ ... ≤ x[n-1] ≤ U

Here n is the number of stored values and U is an upper bound on the largest value.

The monotone order is what makes Elias–Fano possible. If values can jump backward arbitrarily, the high-part representation no longer has the same compact structure.

Strictly increasing sequences are common—for example document IDs or sorted posting lists—but duplicates can also be represented when the implementation defines a nondecreasing contract.

2. Why a sorted list should be compressible

If we store each value independently in 64 bits, a sequence of one million document IDs costs roughly eight megabytes before indexing overhead.

But if the values are sorted inside a known universe, not every combination of 64-bit numbers is possible. The ordering constraint removes information that does not need to be stored repeatedly.

Elias–Fano exploits exactly that structure.

3. Choose how many low bits to keep explicitly

A common choice is:

L = max(0, floor(log2(U / n)))

for nonempty sequences, with careful conventions for zero-size or zero-universe cases.

Then split each number:

low[i]  = x[i] mod 2^L
high[i] = floor(x[i] / 2^L)

Equivalently in bit operations:

low[i]  = x[i] & ((1 << L) - 1)
high[i] = x[i] >> L

The low part keeps the bottom L bits. The high part keeps everything above them.

4. The low bits are easy

Every low part has exactly L bits, so the lows can be packed contiguously:

low[0] | low[1] | low[2] | ... | low[n-1]

This costs exactly nL bits, ignoring word-alignment padding.

There is no delimiter overhead because every field has the same width.

5. The high bits are where the algorithm becomes beautiful

Because the original sequence is nondecreasing, the high parts are also nondecreasing:

high[0] ≤ high[1] ≤ ... ≤ high[n-1]

Instead of writing every high number in binary, place the i-th one-bit at:

position = high[i] + i

The extra +i guarantees that even equal high parts get distinct one-bit positions.

This bitvector simultaneously records order and high-value gaps.

6. A complete worked example

Take:

x = [3, 5, 8, 8, 14]
n = 5
U = 15

Because U/n = 3:

L = floor(log2(3)) = 1

Split the values:

x      high   low
3       1      1
5       2      1
8       4      0
8       4      0
14      7      0

The one-bit positions are:

high[i] + i = [1, 3, 6, 7, 11]

One possible upper bitvector, indexed from zero, is therefore:

0 1 0 1 0 0 1 1 0 0 0 1 0
  ^   ^     ^^       ^

The packed low-bit stream is simply:

1 1 0 0 0

7. Select reconstructs the high part

Let select1(i) return the position of the i-th one-bit, using zero-based rank in this article.

Because the i-th one was stored at high[i] + i:

high[i] = select1(i) - i

Then:

x[i] = (high[i] << L) | low[i]

For the fourth value, i=3:

select1(3) = 7
high[3] = 7 - 3 = 4
low[3] = 0
x[3] = (4 << 1) | 0 = 8

The value emerges without decoding every earlier integer.

8. Why the high bitvector stays small

With the usual choice of L, shifting by L reduces the numerical universe of the high parts to roughly the same scale as the number of stored values.

The upper structure contains exactly n one-bits plus a bounded number of zero-bits representing high-part gaps. This is why the representation approaches the information-theoretic space needed for monotone sequences.

Apache Lucene’s Elias–Fano documentation summarizes the bound as no more than about:

2 + ceil(log2(U/n)) bits per value

under its stated model and parameter choices.

9. Do not reduce Elias–Fano to “compression by gaps”

Gap coding stores differences such as:

x[0], x[1]-x[0], x[2]-x[1], ...

and then compresses those gaps with a variable-length code.

Elias–Fano uses a different architecture. It represents the monotone values directly through a high/low decomposition. This often makes random access and skipping more natural than a purely sequential gap stream.

10. Select is a data-structure operation, not magic

If you scan the upper bitvector from the beginning every time you need the i-th one, reconstruction can become slow.

Practical succinct structures therefore support operations such as:

select1(i): position of the i-th one;
rank1(p): number of one-bits up to a position;
next-set-bit or skip operations;
periodic indexes over upper-bit runs.

The exact time and space depend on the bitvector implementation. Do not claim constant-time predecessor or select unless the supporting index actually provides it.

11. Random access and sequential decoding are different workloads

Sequential decoding can keep state: current high-bit position, current value index and the next packed low field. That can be extremely efficient.

Random access may require select support. Successor queries may use a combination of high-bit navigation and low-bit comparison.

Professional design begins by naming which access pattern matters.

12. Dense sequences may prefer a bitset

If almost every value in the universe is present, a bitset can be simpler and smaller:

bit[value] = 1 if value is present

Elias–Fano is especially attractive when the sequence is monotone and sparse enough that listing values is more economical than representing every universe position.

Lucene’s historical implementation even includes a heuristic for deciding when a fixed bitset may be preferable.

13. Very sparse sequences increase the low-bit width

If U is enormous relative to n, U/n is large and L grows. That means more low bits per value.

This is not a bug. A very sparse set genuinely requires more information to identify each position.

The correct question is not “why did Elias–Fano get bigger?” but “how close is it to the best representation for this density and query workload?”

14. The upper bound U matters

An upper bound that is far larger than the actual maximum can waste space because it increases the chosen L.

If the application knows the true maximum after building the sequence, use a bound close to that maximum. If the structure must stream values online, the construction strategy may need a known bound, buffering, partitioning or a different representation.

15. Duplicates require a clearly stated contract

Many explanations assume strict increase. Some implementations, including historical Lucene Elias–Fano encoders, allow nondecreasing values.

The position formula high[i]+i still separates equal high parts because the index i increases.

However, successor, predecessor and membership semantics with duplicates must be defined deliberately. A compressed container should specify whether it stores a set, a multiset or an ordered sequence.

16. Empty sequences are not a footnote

The formula log2(U/n) is undefined when n is zero.

A production format must define:

how n=0 is encoded;
whether U may also be zero;
whether L is stored explicitly;
what decoding an empty sequence returns;
how indexes represent “no next value.”

Mathematical shorthand does not replace format design.

17. Bit packing introduces machine-level details

Once low bits cross machine-word boundaries, the implementation must extract fields using shifts and masks that are safe for the target integer width.

Test:

L=0;
L=1;
values whose low field straddles a 64-bit boundary;
the largest supported U;
shift counts equal to word width;
serialization endianness if data crosses machines or languages.

18. Rank/select indexes also consume space

A theoretical encoding size that ignores navigation indexes can mislead production decisions.

Measure the whole structure:

low bits + upper bits + select/rank index + object metadata + alignment + allocator overhead

A representation that is optimal on paper may lose to a simpler structure for small lists because fixed overhead dominates.

19. Partitioning can improve locality

Large posting lists are often divided into blocks. Each block can have its own local universe and count, reducing the effective U/n ratio and improving cache locality or skipping behavior.

This creates another trade-off: more block metadata versus smaller local encodings and better navigation.

20. Why search engines care

Inverted indexes store sorted document identifiers, positions and other monotone sequences. Sebastiano Vigna’s quasi-succinct index work showed how Elias–Fano-style representations can support compressed search structures without forcing the conventional gap-code architecture.

The professional lesson is broader than information retrieval: whenever your data is monotone, ask whether order itself can become part of the encoding.

21. A strong teaching sequence uses visible binary structure

For novices, begin with tiny numbers that can be written in binary by hand.

Predict: choose L and split each value into high and low pieces.
Construct: place one-bits at high[i]+i.
Trace: use select positions to reconstruct values.
Explain: say why the added index i preserves duplicate high parts.
Modify: change U or n and predict how L and space change.
Build: implement packing only after the representation is visible.

This follows evidence from programming education that worked examples, subgoal labels and structured read–modify–make progressions reduce unnecessary search for novices.

22. Make learners calculate the space

For every exercise, record:

n
U
L
low-bit count
upper-bit count
index overhead
total bits
bits per value

Compression becomes understandable when learners can explain where every bit went.

23. Compare against honest baselines

Useful baselines include:

64-bit or 32-bit plain arrays;
delta gaps with variable-byte coding;
bitsets;
run-length or bitmap compression where appropriate;
other succinct monotone-sequence structures.

Measure both storage and the operations you actually need: sequential scan, random select, intersection, successor search and construction time.

24. Round-trip tests are only the beginning

At minimum:

decode(encode(x)) == x

for thousands of random monotone sequences.

Then verify indexed operations independently:

select(i) equals the source value at i;
sequential decoder output equals random-access output;
successor queries match binary search on the original array;
duplicates preserve multiplicity when allowed;
serialization round-trips across process boundaries.

25. Generate adversarial densities

Do not benchmark only one friendly distribution. Include:

very dense ranges;
uniform random sparse values;
clustered values;
long duplicate runs if supported;
near-maximum universe values;
tiny n with huge U;
huge n with small gaps.

Representation quality is distribution-sensitive.

26. Measure decode bandwidth and branch behavior

Professional performance can depend on:

bit extraction throughput;
select-index locality;
branch predictability while scanning upper bits;
vectorized popcount or bit-scan instructions;
cache misses across large indexes;
allocation and construction cost.

Bits per value is important, but it is not the whole performance story.

27. Modern research still extends the idea

Elias–Fano is not a museum piece. Recent work continues to study Elias–Fano compression for rank/select structures and modern memory hierarchies. A 2025 SEA paper, for example, examines Elias–Fano compression in space-efficient rank and select structures.

This is a useful lesson for students: a classic algorithmic representation can remain relevant because hardware, datasets and access patterns keep changing.

28. Common failure states

Applying Elias–Fano to an unsorted sequence without first establishing a monotone representation.
Using an absurdly loose U and then blaming the encoding for poor space.
Forgetting that high[i] is recovered as select1(i)-i.
Using inconsistent zero-based and one-based select conventions.
Assuming duplicates are forbidden or allowed without checking the implementation contract.
Ignoring n=0 and L=0 cases.
Claiming O(1) navigation without accounting for the rank/select index.
Reporting theoretical encoded bits while hiding index and object overhead.
Ignoring word-boundary and serialization bugs in bit packing.

29. Beginner-to-professional learning ladder

Beginner: split sorted integers into binary high and low parts.
Foundation: build the upper one-bit positions and reconstruct values by select.
Intermediate: implement packing, sequential decoding and random access.
Advanced: derive the space behavior, add rank/select indexes and support successor-style navigation.
Professional: benchmark against bitsets and gap codes, partition large lists, handle edge cases, validate serialized formats and measure whole-structure memory plus query throughput.

30. Ownership boundary

This article owns the public learning job for Elias–Fano encoding of monotone integer sequences: high/low decomposition, upper unary-style bitvectors, select-based reconstruction, space reasoning and production trade-offs. It complements, but does not replace, broader articles on succinct data structures, compression, search indexes or any learner-state, calibration, interface or private implementation machinery elsewhere in the eduKate ecosystem.

Sources and further reading

Peter Elias, “Efficient Storage and Retrieval by Content and Address of Static Files,” Journal of the ACM 21(2), 1974: DOI.
Sebastiano Vigna, “Quasi-Succinct Indices,” 2012: arXiv; SIGIR version: DOI.
Apache Lucene, EliasFanoEncoder documentation and implementation notes: Lucene.
Hough and Bhatele, “Elias-Fano Compression for Space-Efficient Rank and Select Structures,” SEA 2025: Dagstuhl.
ACM/IEEE-CS/AAAI CS2023, Algorithms and Complexity knowledge area: CS2023.
Computer Science Teachers Association, 2026 standards overview: CSTA.
Sentance, Waite and Kallia, PRIMM programming pedagogy: SIGCSE.
Margulieux, Morrison and Decker, subgoal-labeled worked examples: International Journal of STEM Education.

Professional rule: you understand Elias–Fano when you can explain not only how to reconstruct a value, but why monotonicity lets the positions of one-bits carry information that an ordinary array stores explicitly.

Small Group Tutorials