A Survey of Large-Scale Out-of-Core Graph Processing

Abstract

Through analyzing and mining the relationships among different objects, graph processing is playing an increasingly important role in various application domains, such as social network analysis, product recommendation, and traffic planning. Unfortunately, real-world graphs often exhibit enormous sizes (i.e., trillions of vertices and edges) and complex structures, which makes large-scale in-memory graph processing extremely challenging, if not impractical, and necessitates out-of-core approaches. Therefore, numerous out-of-core graph processing systems have been developed in recent years to efficiently store and process these large graphs. By exploiting the low-cost HDD-/SSD-based external storage and designing disk-friendly graph data placement and execution models, these systems can achieve relatively good performance with low hardware costs, making them a cost-effective solution for large-scale graph analytics. In this article, we conduct a survey on the designs and implementations of out-of-core graph processing systems. Specifically, we review the key techniques in different dimensions of optimization for out-of-core graph processing systems, including graph preprocessing, graph algorithm execution, utilization of emerging storage devices, and miscellaneous optimizations. For each dimension, we analyze the technical challenges and provide critical insights. Furthermore, we explore and discuss the opportunities for future research of out-of-core graph processing systems. This survey will help researchers better understand and gain useful insights into the large and complex design space of out-of-core graph processing.