Pool Compression for Undirected Graphs

Abstract

We present a new graph compression scheme that intrinsically exploits the similarity and locality of references in a graph by first ordering the nodes and then merging the contiguous adjacency lists of the graph into blocks to create a pool of nodes. The nodes in the adjacency lists of the graph are encoded by their position in the pool. This simple yet powerful scheme achieves compression ratios better than the previous methods for many datasets tested in this paper and, on average, surpasses all the previous methods. The scheme also provides an easy and efficient access to neighbor queries, e.g., finding the neighbors of a node, and reachability queries, e.g., finding if node $u$ is reachable from node $v$ . We test our scheme on publicly available graphs of different sizes and show a significant improvement in the compression ratio and query access time compared to the previous approaches.

Keywords

• Graph compression
• merging adjacency lists
• node ordering
• Elias-Gamma encoding