Survey and Taxonomy of Lossless Graph Compression and Space-Efficient Graph Representations

Understand

Various graphs such as web or social networks may contain up to trillions of edges.

• Compressing such datasets can accelerate graph processing by reducing the amount of I/O accesses and the pressure on the memory subsystem.
• Yet, selecting a proper compression method is challenging as there exist a plethora of techniques, algorithms, domains, and approaches in compressing graphs.
• To facilitate this, we present a survey and taxonomy on lossless graph compression that is the first, to the best of our knowledge, to exhaustively analyze this domain.