SuperCSR: A Space-Time-Efficient CSR Representation for Large-scale Graph Applications on Supercomputers

It is widely accepted that graph representations such as the Compressed Sparse Row (CSR) format, directly affect the space and time complexities of graph processing. However, the standard CSR and its current variations are prone to high memory footprint and complicated calculations, which necessitates the development of more efficient graph processing techniques to save memory and reduce calculations. This paper presents SuperCSR, a more space-time-efficient CSR representation for fast graph processing. SuperCSR's key idea is to leverage the law of sorted graphs, which would directly access adjacent vertex sets from an active vertex ID without complex indexing calculations and with a lower memory footprint.