partitioned-elias-fano · shipping · also PEF indexes

Partitioned Elias-Fano

Partitioned Elias-Fano represents a sorted integer sequence in separately encoded chunks with an upper-level index that locates their endpoints and payloads.

Mechanism: Local ranges can expose clustering hidden by one global universe. The 2014 design includes fixed-size and variable-size partitions; dense chunks may use bitmaps or an implicit all-values representation. [1]

Cost: Smaller chunks can reduce payload while increasing endpoint, size and location metadata. The published optimization includes a per-chunk cost; minimizing only payload is a different objective. [1]

Example: A toy two-partition recipe uses 124 bits for clustered input but 284 for spread input, versus 224 for either unpartitioned payload. Both inputs contain 32 identifiers spanning 0 through 1039. Each partition is rebased to its first value and all declared toy headers are counted. This is an arithmetic illustration, not the paper's wire format or a speed benchmark. [3]

Relations

related
Elias-Fano encoding, Roaring bitmap

Citations

  1. Giuseppe Ottaviano and Rossano Venturini, Partitioned Elias-Fano Indexes, SIGIR 2014, sections 4-5; DOI 10.1145/2600428.2609615 (accessed 2026-11-17)
  2. Authors' historical implementation and experiment repository (accessed 2026-11-17)
  3. Hesela: exact Elias-Fano payload and explicit toy partition-header accounting (CC0) (accessed 2026-11-17)

Further reading

  1. Hesela: compressed indexes and the metadata needed to read them (accessed 2026-11-17)
Sources & caveats
  • SIGIR 2014 evaluates document identifiers and term frequencies, not positional postings; its performance results concern its recorded corpora and implementations. [1]
  • The historical code links to its successor ds2i. No upstream implementation or figure was copied. [2]

JSON: /data/terms/partitioned-elias-fano.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Partitioned Elias-Fano. Hesela. 2026-11-17. https://hesela.dev/terms/partitioned-elias-fano/