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
- Giuseppe Ottaviano and Rossano Venturini, Partitioned Elias-Fano Indexes, SIGIR 2014, sections 4-5; DOI 10.1145/2600428.2609615
- Authors' historical implementation and experiment repository
- Hesela: exact Elias-Fano payload and explicit toy partition-header accounting (CC0)