File EliasFano.h

↰ Parent directory (ADS/succinct)

The Elias-Fano representation of a non-decreasing sequence :math:` x_0 le cdots le x_{n-1} ` of integers in :math:` [ 0 , u ) ` (section 11.6 and 15.1.2 of the notes): each item is split into its :math:` ell = lceil log_2 ( u / n ) rceil ` low bits, written one after the other in L, and its high bits, the bucket :math:` x_i gg ell , written in H as the unary counts of the buckets ( :math: 1^c 0 ` for a bucket of c items), so that the i-th 1 of H is at the place :math:` ( x_i gg ell ) + i `.

Definition (ADS/succinct/EliasFano.h)

Detailed Description

H has n 1s and at most n 0s, and the sequence takes less than :math:` 2 n + n lceil log_2 ( u / n ) rceil ` bits whatever its distribution (Theorem 11.1), within 2 bits per item of the :math:` log_2 binom{u}{n} ` bits needed to tell n items of :math:` [ 0 , u ) ` apart.

With rank and select on H [see File RankSelect.h] the sequence is not only decoded but searched in place:

  • access( i ), :math:` x_i ` in O( 1 ) time, as :math:` ( select_1( i + 1 ) - i ) ` followed by the i-th field of L;

  • nextGEQ( x ), the place of the first item :math:` ge x , which is the rank of x (the items :math: < x ) and gives the predecessor and the successor: :math: select_0 ` of the bucket of x gives the first item of that bucket, and the scan stops at its end, in O( 1 + c ) time for a bucket of c items, expected O( 1 ) since :math:` 2^ell approx u / n ; past 8 items (the clusters of a sequence fill some buckets) the end of the bucket is found by :math: select_0 ` too and its low bits, sorted, by a binary search, :math:` O( log c ) ` time;

  • viewed as the places of the 1s of a vector of bits B of u bits with n 1s (section 15.1.2), access( i ) is :math:` select_1( i + 1 ) ` of B and nextGEQ( i ) is :math:` rank_1( i ) ` of B, in :math:` n ( 2 + log ( u / n ) ) + o( n ) ` bits rather than u + o( u ) (Theorem 15.5).

The notes compute the rank of B by a binary search on select (Algorithm 15.1), in O( log n ) time; the bucket found by :math:` select_0 ` makes it O( 1 ) expected, the design of Vigna’s quasi-succinct indices and of Okanohara and Sadakane’s sdarray. H is written with the 1s for the items and the 0s for the buckets, as in chapter 11 (section 15.1.2 swaps them, which only swaps :math:` select_0 ` and :math:` select_1 ). The representation ignores the regularities of the sequence: the partitioned Elias-Fano of Ottaviano and Venturini splits it into chunks, each one coded at its own best, and comes within a few percent of the interpolative code [see :ref:`file_ADS_compression_IntegerCodes.h] keeping the random access.

The contracts [see File Contract.h]: the sequence is non-decreasing (an audit) and below u, and access() needs i < n; the audit of the construction is that access() gives back each item, and the postcondition of nextGEQ() is that the items before the place are :math:` < x ` and the one at it is not. The functions are defined in EliasFano.tpp.

  1. Ferragina, Pearls of Algorithm Engineering, Cambridge University Press, 2023, chapters 11 and 15

  1. Elias, Efficient storage and retrieval by content and address of static files, Journal of the ACM 21(2), 246-260, 1974, doi:10.1145/321812.321820

    1. Fano, On the number of bits required to implement an associative memory, Memorandum 61, Computation Structures Group, MIT, 1971

  1. Okanohara, K. Sadakane, Practical entropy-compressed rank/select dictionary, Proc. 9th ALENEX, 60-70, 2007, doi:10.1137/1.9781611972870.6

  1. Vigna, Quasi-succinct indices, Proc. 6th WSDM, 83-92, 2013, doi:10.1145/2433396.2433409

  1. Ottaviano, R. Venturini, Partitioned Elias-Fano indexes, Proc. 37th SIGIR, 273-282, 2014, doi:10.1145/2600428.2609615

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes

Typedefs