Fast and Compact Web Graph Representations Authors: Francisco Claude, Gonzalo Navarro Keywords: Compression, Web Graph, Data Structures
Abstract:
Compressed graph representations, in particular for Web graphs, have become an attractive research topic because of their applications in the manipulation of huge graphs in main memory. The state of the art is well represented by the WebGraph project, where advantage is taken of several particular properties of Web graphs to offer a trade-off between space and access time. In this paper we show that the same properties can be exploited with a different and elegant technique that builds on grammar-based compression. In particular, we focus on Re-Pair and on Ziv-Lempel compression, which, although cannot reach the best compression ratios of WebGraph, achieve much faster navigation of the graph when both are tuned to use the same space. Moreover, the technique adapts well to run on secondary memory and in distributed scenarios. As a byproduct, we introduce an approximate Re-Pair version that works efficiently with severely limited main memory.
Software & Examples: Fast and Compact Web Graph Representations
As topic maps grow larger and/or memory space becomes smaller (comparatively speaking), compressed graph work becomes increasingly relevant.
Gains in navigation speed are always welcome.
[…] WebGraph was mentioned in the article Fast and Compact Web Graph Representations. […]
Pingback by WebGraph « Another Word For It — October 7, 2010 @ 5:56 am