I/O-Efficient Graph Analytics on SSD via Activity-Aware Preprocessing

Abstract

SSD-based graph processing systems provide a cost-efficient solution for handling ever-growing large graphs that cannot fit into the memory of a single machine. However, the mismatch between the coarse SSD access granularity (e.g., 4 KB) and the fine-grained graph vertex data causes severe read amplification and poor I/O efficiency. Prior efforts, such as dynamic active data gathering and reordering-based graph preprocessing, partially alleviate this issue but often introduce expensive online overheads, inefficient graph traversal, and I/O imbalance, thereby degrading overall system performance. To address these limitations, we present Graphago, an activity-aware graph preprocessing technique for SSD-based graph processing systems. Graphago optimizes the graph storage organization by jointly exploiting the predicted activity of graph data through three coordinated designs, thereby improving I/O efficiency without compromising overall processing performance. First, it employs a dual-centrality activity prediction model that accurately estimates vertex activity by capturing both local connectivity and global importance. Second, it introduces an activity-neighborhood graph ordering technique that reorganizes the graph according to vertex activity and neighborhood relationships, reducing read amplification while preserving traversal efficiency. Third, it adopts an active-data-balanced graph partitioning scheme that distributes high-activity data evenly across partitions to mitigate I/O imbalance. Furthermore, we extend Graphago to support dynamic graph processing through a suite of lazy-adaptive, activity-aware mechanisms. Experimental results show that Graphago outperforms state-of-the-art SSD-based graph processing systems by up to 4.8×, while delivering higher I/O efficiency with reasonable preprocessing overhead.