View publication
Title | K2-trees for Compact Web Graph Representation |
Authors | Nieves Brisaboa, Susana Ladra, Gonzalo Navarro |
Publication date | 2009 |
Abstract | 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. |
Pages | 18-30 |
Conference name | International Symposium on String Processing and Information Retrieval |
Publisher | Springer-Verlag (Berlin/Heidelberg, Germany) |
Reference URL |