File BVGraph.h

↰ Parent directory (ADS/succinct)

The compression of the adjacency lists of Boldi and Vigna (section 15.3.1 of the notes), designed for the Web graphs, whose nodes are the pages sorted by URL: locality (most links stay in the host, so that the successors of x are close to x and to each other) and similarity (the pages of a host link to the same pages).

Definition (ADS/succinct/BVGraph.h)

Detailed Description

The list of x is written as:

  • its outdegree, in :math:` gamma ` [see File IntegerCodes.h];

  • the reference r: the list of x - r, among the previous W lists (the window), that shares the most successors with that of x, 0 for none;

  • the copy list of the reference, a bit per successor of x - r telling whether it is a successor of x too, written as copy blocks: its first bit, then the lengths less 1 of its runs, the last one omitted since the outdegree of the reference tells it (Tables 15.5 and 15.6);

  • the extra nodes, the successors not copied: the runs of at least :math:` L_{min} ` consecutive integers as intervals, the left extreme as a gap from the previous right extreme less 2 (the first one from x, by signedToNatural()) and the length less :math:` L_{min} , then the residuals as gaps less 1 (the first one from x, by signedToNatural()), in :math: delta ` (Table 15.7).

A list is decoded from its place in the stream, kept for every node in an Elias-Fano sequence [see File EliasFano.h], after the list of its reference; the chains of references are at most R long, so that a list is decoded in :math:` O( R d ) ` time for outdegrees up to d. With the window W = 7, the chains R = 3 and :math:` L_{min} = 4 ` (the defaults of the WebGraph framework) the Web graphs take about 3 bits per edge, against the :math:` log_2 n ` bits of a plain list and the :math:` 2 + log ( n^2 / m ) ` of Elias-Fano [see File EliasFanoGraph.h]; the :math:` k^2 -tree [see :ref:`file_ADS_succinct_K2Tree.h] is comparable in space and also gives the predecessors. The WebGraph framework codes the gaps by the :math:` zeta ` codes, tuned to their power-law distribution, and reorders the nodes (e.g., by layered label propagation) to make locality stronger; neither is in the notes.

copyList(), copyBlocks(), intervals() and residualGaps() are the steps of the coding, given for the examples of the notes.

The contracts [see File Contract.h]: each list is strictly increasing (an audit) with its nodes in [ 0 , n ), the window and the chains are at least 1 and :math:` L_{min} ge 2 `; the audit of the construction is that each list is decoded back. The functions are defined in BVGraph.tpp.

  1. Ferragina, Pearls of Algorithm Engineering, Cambridge University Press, 2023, chapter 15

  1. Boldi, S. Vigna, The WebGraph framework I: compression techniques, Proc. 13th WWW, 595-602, 2004, doi:10.1145/988672.988752

  1. Boldi, M. Rosa, M. Santini, S. Vigna, Layered label propagation: a multiresolution coordinate-free ordering for compressing social networks, Proc. 20th WWW, 587-596, 2011, doi:10.1145/1963405.1963488

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes