File EliasFanoGraph.h

↰ Parent directory (ADS/succinct)

A static directed graph whose adjacency lists are coded by Elias-Fano [see File EliasFano.h] (section 15.3.2 of the notes), the representation of the adjacency lists of large graphs in Facebook’s Unicorn and in the quasi-succinct indices of Vigna.

Definition (ADS/succinct/EliasFanoGraph.h)

Detailed Description

The edge :math:` ( u , v ) ` of a graph of n nodes is the integer :math:` u n + v , so that the lists, each one sorted, are one increasing sequence in :math: [ 0 , n^2 ) , and the prefix sums of the outdegrees are a second sequence that tells where the list of u starts; with m edges the graph takes about :math: m ( 2 + lceil log_2 ( n^2 / m ) rceil ) + n ( 2 + lceil log_2 ( m / n ) rceil ) ` bits, plus the directories, and answers in O( 1 ) time the outdegree and the i-th successor of a node, and the existence of an edge by nextGEQ() in O( 1 ) expected time.

The notes code each list on its own, with its own universe: since :math:` sum_u d_u log ( n / d_u ) le m log ( n^2 / m ) ` by the concavity of the logarithm, the lists alone can take fewer bits when the degrees are skewed, at the price of a directory and an offset per list; the single sequence here keeps one directory and the same O( 1 ) access. Neither exploits the locality and the similarity of the lists of the Web, which the codes of Boldi and Vigna do [see File BVGraph.h], nor the clustering of the adjacency matrix, which the :math:` k^2 -tree does [see :ref:`file_ADS_succinct_K2Tree.h].

The contracts [see File Contract.h]: each list is strictly increasing (an audit) with its nodes in [ 0 , n ), :math:` n^2 ` fits in 64 bits, and the nodes and the places asked for exist. The functions are defined in EliasFanoGraph.tpp.

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

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

  1. Curtiss et al., Unicorn: a system for searching the social graph, Proc. VLDB Endowment 6(11), 1150-1161, 2013, doi:10.14778/2536222.2536239

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes