Pool Compression for Undirected Graphs
Lists
Only you see this
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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$u$ </tex-math></inline-formula> is reachable from node <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$v$ </tex-math></inline-formula> . 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.
BibTeX
@inproceedings{yousuf2022pool,
author = {Muhammad Irfan Yousuf and Suhyun Kim},
title = {{Pool Compression for Undirected Graphs}},
booktitle = {IEEE Access},
year = {2022},
url = {https://openreview.net/forum?id=K3O7EpTP0o0},
}Loading related content...