An Efficient Graph Compressor Based on Adaptive Prefix Encoding

Abstract

In this paper we introduce APEC, a graph compression/decompression framework. A key component of APEC is adaptive prefix code, a novel variable-length coding scheme which can adapt to varying characteristics of different vertices in the graph data. APEC also encompasses many software optimization techniques including compressed vertex indexing, bit counting and parallelization. The net outcome is that APEC not only achieves up to 20% improvement on compression ratio, which is equivalent to 2.28 bits/edge, but also as much as 9x faster in compression and up to 20x faster in decompression compared to the existing frameworks. Moreover, APEC is capable of random accessing compressed data and performing compression on extremely large graph datasets.