Compact representation of Web graphs with extended functionality

作者：

Highlights：

• We present k2-tree, a compact representation of Web graphs.

• It obtains the smallest space of the state of the art, supporting random navigation.

• It exploits the sparseness and clustering of the adjacency matrices of Web graphs.

• It supports successors and predecessors, and also single-link and range queries.

摘要

Highlights•We present k2-tree, a compact representation of Web graphs.•It obtains the smallest space of the state of the art, supporting random navigation.•It exploits the sparseness and clustering of the adjacency matrices of Web graphs.•It supports successors and predecessors, and also single-link and range queries.

论文关键词：Web graphs,Compact data structures

论文评审过程：Received 27 January 2013, Revised 22 June 2013, Accepted 4 August 2013, Available online 21 August 2013.

论文官网地址：https://doi.org/10.1016/j.is.2013.08.003