Kedagraph: memory-efficient out-of-core graph processing system with high applicability

Abstract Increases in the complexity and detail of real-world graphs have engendered difficulties in reducing the memory and processing requirements of these graphs. Various distributed and single computer processing systems have been developed for processing large graphs. Out-of-core processing systems achieve enhanced processing efficiency by reducing input–output (I/O) processing requirements, increasing locality, or accelerating convergence. However, not all out-of-core systems can optimize every graph processing algorithm. Accordingly, this study proposes KedaGraph, an out-of-core graph processing system that offers three streamers to enhance its applicability across different algorithms. In addition, this system enables more flexible scheduling than do existing out-of-core processing systems, thus facilitating improved performance in different processing tasks. We also developed a compression scheme to reduce the I/O overhead of KedaGraph. Our evaluation results revealed that KedaGraph outperformed existing out-of-core systems in various graph processing tasks. Furthermore, the proposed system demonstrates sensitivity to memory budget and thread count on commodity single-node hardware, with performance improvements observed as available resources increase within the evaluated configuration range.