A posting list is already half an index.

For a term in a search engine, the document IDs arrive sorted:

3, 4, 7, 13, 14, 15, 21, ...

The classical compression move is to store gaps:

3, 1, 3, 6, 1, 1, 6, ...

Small gaps get short codes. That is a good instinct. It is also a sequential instinct: to find the 10,000th posting or skip to the first posting at least x, the decoder often has to walk through earlier codes or auxiliary skip blocks.

Elias-Fano takes a different route. It treats the sorted list as a monotone sequence and stores the absolute values in two pieces:

low bits:  literal fixed-width suffixes
high bits: a unary bitmap with select support

The representation is not just a compressed byte stream. It is a compressed addressing scheme.

The construction is usually traced to Peter Elias’s work on static files and Robert Fano’s independent work on associative memory.1

Split Each Value

Let the list contain \(n\) integers:

\[0 \le x_0 < x_1 < \cdots < x_{n-1} < U.\]

Pick:

\[\ell = \left\lfloor \log_2(U/n) \right\rfloor.\]

Write each value as:

\[x_i = h_i 2^\ell + l_i,\]

where \(l_i\) is the low \(\ell\)-bit suffix and \(h_i\) is the remaining high part.

The low parts are easy:

l_0, l_1, l_2, ...

stored in fixed width. This costs \(n\ell\) bits.

The high parts are monotone. Elias-Fano stores them by setting one bit per element in an upper bitmap:

H[h_i + i] = 1.

That + i is the little translation that keeps equal high parts from colliding. If several values share the same high part, their one-bits appear consecutively. Zeros in the bitmap mark high-part buckets with no value or with a boundary between groups.

To read the \(i\)th value, select the \(i\)th one-bit in H:

\[h_i = \operatorname{select}_1(H, i) - i.\]

Then attach the stored low suffix:

\[x_i = h_i 2^\ell + l_i.\]

That is the whole shape. The high bits are not decoded by replaying gaps. They are recovered by a select query.

The Space Bargain

The exact bit count in the lab is:

\[n\ell + n + \left\lfloor \frac{U-1}{2^\ell} \right\rfloor + 1.\]

The first term is the low-bit array. The rest is the upper bitmap: one bit for each element plus enough zero slots to name the high buckets.

With the usual choice of \(\ell\), this is close to:

\[n \log_2(U/n) + O(n)\]

bits. Lucene’s Elias-Fano encoder documentation phrases the engineering bound as at most roughly 2 + ceil(log2(upperBound / numValues)) bits per encoded number, under its upper-bound convention.2

That is why the representation is attractive for sparse monotone lists. A raw fixed-width array spends \(\lceil \log_2 U \rceil\) bits per value. A bitset spends \(U\) bits whether the term appears in ten documents or ten million. Elias-Fano spends bits according to the average spacing.

The catch is density. If the list is very dense, a bitset can win. Vigna’s quasi-succinct index paper makes this engineering point explicitly by switching to ranked characteristic bitvectors for dense cases.3 Lucene’s docs make a similar practical comparison against fixed bitsets.2

So the right slogan is not “Elias-Fano beats bitsets.” It is:

Elias-Fano is a sparse monotone sequence layout with useful navigation baked in.

The Lab

The lab below builds deterministic synthetic posting lists, encodes them with Elias-Fano, and compares the bit budget against three baselines:

  • fixed-width absolute document IDs;
  • a full universe bitset;
  • byte-aligned varint gaps; and
  • the Elias-Fano split itself.

It also checks two operations:

  • access(i), by decoding select1(i) - i plus the low bits; and
  • nextGEQ(target), implemented here as a binary search over decoded access.

That nextGEQ implementation is intentionally simple. Production structures avoid decoding one item at a time by adding rank/select samples, broadword search, and skip pointers. The point of the artifact is to expose the invariant, not to pretend a few dozen lines of JavaScript is a tuned search engine.

Elias-Fano low bits high bits skip target

The lab has a built-in audit. It reports 35 named checks: decode, monotonicity, high-bit placement, one-bit count, direct access, nextGEQ, and target-sweep lower bounds across five scenarios:

node - <<'NODE'
const lab = require("./assets/js/elias-fano-lab.js");
const EXPECTED_CASE_KEYS = [
  "1:default-clustered:100000:900:6",
  "2:uniform:4096:64:6",
  "3:clustered:100000:1500:6",
  "4:dense:2048:1200:0",
  "5:runs:250000:2200:6"
];
const EXPECTED_CASE_ROWS = [
  "1:default-clustered:100000:900:l=6:ef=8.74:varbyte=10.57:target=true:checks=7/7:passed=true",
  "2:uniform:4096:64:l=6:ef=8.00:varbyte=8.00:target=true:checks=7/7:passed=true",
  "3:clustered:100000:1500:l=6:ef=8.04:varbyte=9.02:target=true:checks=7/7:passed=true",
  "4:dense:2048:1200:l=0:ef=2.71:varbyte=8.01:target=true:checks=7/7:passed=true",
  "5:runs:250000:2200:l=6:ef=8.78:varbyte=8.35:target=true:checks=7/7:passed=true"
];
const EXPECTED_CHECK_SHAPE = [
  { name: "decode", ok: true },
  { name: "monotone-input", ok: true },
  { name: "high-bit-positions", ok: true },
  { name: "one-bit-count", ok: true },
  { name: "access-query", ok: true },
  { name: "next-geq-query", ok: true },
  { name: "target-sweep", ok: true }
];
const EXPECTED_CASES = EXPECTED_CASE_KEYS.length;
const EXPECTED_CHECKS = EXPECTED_CASES * EXPECTED_CHECK_SHAPE.length;

function sameList(left, right) {
  return left.length === right.length &&
    left.every((value, index) => value === right[index]);
}

function sameJson(left, right) {
  return JSON.stringify(left) === JSON.stringify(right);
}

function rowDrifts(actual, expected) {
  const count = Math.max(actual.length, expected.length);
  const drift = [];
  for (let index = 0; index < count; index += 1) {
    if (actual[index] !== expected[index]) {
      drift.push({ index, actual: actual[index], expected: expected[index] });
    }
  }
  return drift;
}

function auditShape(audit) {
  return {
    cases: audit.cases.map(
      (row) => `${row.caseId}:${row.scenario}:${row.universe}:${row.count}:${row.l}`
    ),
    caseRows: audit.cases.map(
      (row) => `${row.caseId}:${row.scenario}:${row.universe}:${row.count}:` +
        `l=${row.l}:ef=${row.bitsPerValue.toFixed(2)}:` +
        `varbyte=${row.varbyteBitsPerValue.toFixed(2)}:` +
        `target=${row.targetOk}:checks=${row.passedChecks}/${row.totalChecks}:` +
        `passed=${row.passed}`
    ),
    checksByCase: audit.cases.map((row) =>
      row.checks.map((check) => ({
        name: check.name,
        ok: check.ok
      }))
    )
  };
}

const audit = lab.auditEliasFanoLab();
const shape = auditShape(audit);
const failed = audit.cases.filter(
  (row) => !row.passed || row.passedChecks !== row.totalChecks
);
const caseRowDrifts = rowDrifts(shape.caseRows, EXPECTED_CASE_ROWS);
const shapeErrors = [
  sameList(shape.cases, EXPECTED_CASE_KEYS) ? null : "cases",
  caseRowDrifts.length ? "caseRows" : null,
  shape.checksByCase.every((checks) => sameJson(checks, EXPECTED_CHECK_SHAPE))
    ? null
    : "checksByCase"
].filter(Boolean);
console.table(audit.cases.map((row) => ({
  scenario: row.scenario,
  universe: row.universe,
  count: row.count,
  l: row.l,
  efBitsPerValue: row.bitsPerValue.toFixed(2),
  varbyteBitsPerValue: row.varbyteBitsPerValue.toFixed(2),
  checks: `${row.passedChecks}/${row.totalChecks}`,
  targetOk: row.targetOk,
  passed: row.passed
})));
const summary =
  `${audit.passed}/${audit.total} scenarios and ` +
  `${audit.passedChecks}/${audit.totalChecks} checks passed`;
if (
  shapeErrors.length ||
  audit.total !== EXPECTED_CASES ||
  audit.totalChecks !== EXPECTED_CHECKS ||
  failed.length ||
  !audit.ok ||
  audit.passed !== audit.total ||
  audit.passedChecks !== audit.totalChecks
) {
  throw new Error(JSON.stringify({
    summary,
    shapeErrors,
    shape,
    drifts: { caseRows: caseRowDrifts },
    failed,
    errors: audit.errors,
    expectedCases: EXPECTED_CASES,
    expectedChecks: EXPECTED_CHECKS,
    total: audit.total,
    totalChecks: audit.totalChecks
  }, null, 2));
}
console.log(summary);
NODE

The checks cover uniform, clustered, dense, and run-heavy lists. They assert that:

  • decoding every index reproduces the original sorted list;
  • every one-bit is at position high(x[i]) + i;
  • the number of one-bits equals the number of postings;
  • access(i) agrees with the original list; and
  • nextGEQ(target) agrees with a naive lower-bound scan.

Vigna’s quasi-succinct index paper begins with a contrast against ordinary gap-compressed inverted indexes: document pointers are stored in increasing order, and gap compression gives small gaps short codes, but the proposed index uses a quasi-succinct representation of monotone sequences instead.3

That change matters because query engines do not only enumerate postings. They also skip. A conjunctive query needs to keep several posting lists aligned:

advance the shorter list to at least the current document of the longer list

If the compressed representation supports access and nextGEQ cheaply, the index can stay compressed while still behaving like an addressable object.

This is the reason Elias-Fano keeps reappearing in search systems, graph compression, and succinct libraries. The high bitmap is not decorative. It is where the navigation lives.

What This Toy Does Not Include

The JavaScript lab stores the select1 positions explicitly. That would be wasteful in a real compressed index. Production implementations store sampled rank/select support, use word-level bit tricks, and often add skip pointers. Vigna describes longword addressing and broadword bit search as key engineering pieces for query speed.3

The lab also encodes one list at a time. Modern variants exploit clustering and partitioning. Ottaviano and Venturini’s partitioned Elias-Fano work describes a two-level representation that improves the compression/time tradeoff, especially when posting lists have locally clustered regions.4 Pibiri and Venturini later show that clustering related posting lists can reduce redundancy across lists, while still building on Elias-Fano representations of monotone sequences.5

Those refinements do not change the core picture:

low bits carry local offsets
high bits carry a selectable map

Once you see that split, Elias-Fano stops looking like just another integer codec. It is a way to store a sorted list so that the compressed form still has addresses.

  1. Original sources: Peter Elias, “Efficient Storage and Retrieval by Content and Address of Static Files”, Journal of the ACM 21(2), 1974; Robert M. Fano, “On the Number of Bits Required to Implement an Associative Memory”, MIT Project MAC Memorandum 61, 1971. ↩

  2. Apache Lucene 4.10.2 API documentation for EliasFanoEncoder. The docs describe the high-bits/low-bits representation, the choice of L, the bits-per-number bound, and the comparison with fixed bitsets. ↩ ↩2

  3. Sebastiano Vigna, “Quasi-Succinct Indices”, WSDM 2013; arXiv page. Vigna applies Elias-Fano-style monotone sequence representations to inverted indexes and discusses random access, skipping, and broadword engineering. ↩ ↩2 ↩3

  4. Giuseppe Ottaviano and Rossano Venturini, “Partitioned Elias-Fano Indexes”, SIGIR 2014. The abstract describes a two-level representation that partitions lists and encodes chunks and endpoints with Elias-Fano. ↩

  5. Giulio Ermanno Pibiri and Rossano Venturini, “Clustered Elias-Fano Indexes”, ACM Transactions on Information Systems. The paper reviews Elias-Fano for monotone sequences, gives the H and L encoding layout, and studies clustered posting-list representations. ↩