File PartitionedEliasFano.h

↰ Parent directory (ADS/succinct)

The partitioned Elias-Fano representation of Ottaviano and Venturini: a strictly increasing sequence :math:` x_0 < cdots < x_{n-1} ` of integers of :math:` [ 0 , u ) ` cut into blocks of B = 128 items, each one coded in the cheapest of three ways relative to the end of the block before, so that a sequence with clusters (the lists of an inverted index) takes far fewer bits than the :math:` 2 + lceil log_2 ( u / n ) rceil ` per item of Elias-Fano [see File EliasFano.h], which ignores its regularities, with the same access and nextGEQ.

Definition (ADS/succinct/PartitionedEliasFano.h)

Detailed Description

The block j holds the items of places :math:` [ j B , ( j + 1 ) B ) , m of them, relative to :math: b_j = x_{j B - 1} + 1 ` (0 for the first block): the values :math:` v = x - b_j ` are in :math:` [ 0 , u_j ) ` with :math:` u_j = x_{mathrm{last}} - b_j + 1 `, and the block is

  • full, with no bit, if :math:` u_j = m ` (every value is there);

  • a vector of :math:` u_j ` bits, the bit v for the value v, if :math:` u_j ` is at most the bits of Elias-Fano;

  • else Elias-Fano with :math:` ell = lfloor log_2 ( u_j / m ) rfloor , in :math: m ell + m + lfloor ( u_j - 1 ) / 2^ell rfloor + 1 ` bits;

the kind is a function of :math:` ( m , u_j ) . For each block a record of fixed width holds the last item, the place of the code of the block and its kind with :math: ell ` (8 bits, so that a query computes no logarithm), and the last item of every 8-th block is kept apart for the searches; so

  • access( i ) reads the records of the block of i and of the one before (next to each other) and selects the item in the code of the block, a scan of its few words (at most :math:` 2 B ` bits of high part, or a vector of :math:` u_j le B ( ell + 3 ) ` bits, since it is chosen only when not longer than Elias-Fano);

  • nextGEQ( x ) finds the first block whose last item is at least x by a search of the items apart in the layout of Eytzinger (a complete binary tree by levels, the node t with the children 2t and 2t + 1, whose descent fetches ahead the nodes three levels down) and then by at most 8 records, and the item in that block by the high part (the 0 of the bucket of x) or by the sideways sums of the vector up to x.

Ottaviano and Venturini also choose the ends of the blocks by an approximate dynamic program on the cost of the codes, which gains a further 10% or so on the lists of an index; the blocks here have the fixed size of their uniform partition.

The contracts [see File Contract.h]: the sequence is strictly increasing (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 PartitionedEliasFano.tpp.

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

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

P.-V. Khuong, P. Morin, Array layouts for comparison-based searching, ACM Journal of Experimental Algorithmics 22, 1-39, 2017, doi:10.1145/3053370

    1. Pibiri, R. Venturini, Techniques for inverted index compression, ACM Computing Surveys 53(6), 125, 2020, doi:10.1145/3415148

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes