Fast and Compact Web Graph Representations
Francisco Claude and Gonzalo Navarro
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 tradeoff 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.