K2-trees for Compact Web Graph Representation
Nieves Brisaboa, Susana Ladra, and Gonzalo Navarro
This paper presents a Web graph representation based on a compact tree
structure that takes advantage of large empty areas of the adjacency matrix
of the graph. Our results show that our method is competitive with the best
alternatives in the literature, offering a very good compression ratio
(3.3-5.3 bits per link) while permitting fast navigation on the graph to
obtain direct as well as reverse neighbors (2-15 microseconds per neighbor
delivered). Moreover, it allows for extended functionality not usually
considered in compressed graph representations.