Succinct dual clique cover representations allow fundamental graph algorithms to run in time proportional to the representation size instead of the number of edges, delivering substantial memory savings and speedups on real-world graphs with dense local cliques.
Survey and Taxonomy of Lossless Graph Compression and Space-Efficient Graph Representations
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
abstract
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. Moreover, our survey does not only categorize existing schemes, but also explains key ideas, discusses formal underpinning in selected works, and describes the space of the existing compression schemes using three dimensions: areas of research (e.g., compressing web graphs), techniques (e.g., gap encoding), and features (e.g., whether or not a given scheme targets dynamic graphs). Our survey can be used as a guide to select the best lossless compression scheme in a given setting.
fields
cs.DS 2verdicts
UNVERDICTED 2representative citing papers
A clique-partitioning preprocessing algorithm that replaces bipartite cliques with tripartite graphs to reduce edge count and accelerate downstream graph algorithms, with claimed O(m n^δ) time and up to 74% edge reduction on large instances.
citing papers explorer
-
Succinct Graph Representations and Algorithmic Applications
Succinct dual clique cover representations allow fundamental graph algorithms to run in time proportional to the representation size instead of the number of edges, delivering substantial memory savings and speedups on real-world graphs with dense local cliques.
-
Speeding-up Graph Algorithms via Clique Partitioning
A clique-partitioning preprocessing algorithm that replaces bipartite cliques with tripartite graphs to reduce edge count and accelerate downstream graph algorithms, with claimed O(m n^δ) time and up to 74% edge reduction on large instances.