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

摘要: Various graphs such as web or social networks may contain up to trillions of edges. Compressing datasets can accelerate graph processing by reducing the amount I/O accesses and pressure on memory subsystem. Yet, selecting a proper compression method is challenging there exist plethora techniques, algorithms, domains, approaches in compressing graphs. To facilitate this, we present survey taxonomy lossless that first, best our knowledge, exhaustively analyze this domain. Moreover, does not only categorize existing schemes, but also explains key ideas, discusses formal underpinning selected works, describes space schemes using three dimensions: areas research (e.g., graphs), techniques gap encoding), features whether given scheme targets dynamic graphs). Our be used guide select setting.