File K2Tree.h

↰ Parent directory (ADS/succinct)

The :math:` k^2 -tree of Brisaboa, Ladra and Navarro (section 15.3.3 of the notes): the adjacency matrix of a graph of n nodes, padded to the side :math: N = k^h ge n , is split into :math: k^2 ` submatrices of side N / k, each one a child of the root marked 1 if it has an edge and 0 otherwise, and each child marked 1 is split again, down to the cells.

Definition (ADS/succinct/K2Tree.h)

Detailed Description

The marks are written by levels: T has those of all the levels but the last, L those of the cells, and with rank on T [see File RankSelect.h] the children of the node marked at the place p of T start at the place :math:` rank_1( p + 1 ) k^2 ` of T followed by L, as in LOUDS [see File LoudsTree.h]: no pointer is stored.

neighbors( u ) walks down the children that cross the row u (k of the :math:` k^2 ` at each level) and reverseNeighbors( v ) those that cross the column v, so that the same bits give the successors and the predecessors, which the lists give only by doubling them; hasEdge( u , v ) follows one path, in O( h ) time. A row is read in :math:` O( sqrt{m} ) ` time on average for m edges spread uniformly, O( n ) in the worst case (Theorem 15.8), and the tree takes :math:` k^2 m ( log_{k^2} ( n^2 / m ) + O( 1 ) ) ` bits in the worst case (Theorem 15.9), far fewer when the edges are clustered, as in the Web graphs ordered by URL, where the submatrices of zeros are large. A larger k gives fewer levels and faster queries, a smaller one fewer bits; the authors use a larger k at the top levels and a smaller one below, and the construction here works from the edges, by levels, in :math:` O( m h ) ` time, without the matrix that the recursive construction of the notes (Algorithm 15.3) visits whole.

The contracts [see File Contract.h]: :math:` k ge 2 `, the edges join nodes in [ 0 , n ), and the nodes asked for exist; the postcondition of the construction is that the tree has as many cells marked as distinct edges. The functions are defined in K2Tree.tpp.

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

    1. Brisaboa, S. Ladra, G. Navarro, k2-trees for compact web graph representation, Proc. 16th SPIRE, LNCS 5721, 18-30, 2009, doi:10.1007/978-3-642-03784-9_3

    1. Brisaboa, S. Ladra, G. Navarro, Compact representation of Web graphs with extended functionality, Information Systems 39, 152-174, 2014, doi:10.1016/j.is.2013.08.003

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes