Gem: Scalable Monotonic Graph Processing Beyond Billion-Scale on a Single Machine
Open Access
- 4 December 2025
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 3 (6) , 1-30
Abstract
Monotonic graph algorithms, such as shortest path, BFS, and reachability, are fundamental to graph analytics and are widely used across domains. Recent systems employ pruning techniques to accelerate the processing of these algorithms. However, state-of-the-art monotonic graph engines are restricted to in-memory execution and cannot scale to graphs that exceed main memory capacity. In contrast, existing out-of-core graph engines are designed for general-purpose workloads and lack effective pruning mechanisms tailored to monotonic graph algorithms. To bridge this gap, we present Gem, an out-of-core graph engine designed for monotonic graph algorithms. Gem introduces a PageRank-based graph sketch that captures key topological features inmemory with minimal preprocessing overhead. Building on this sketch, we propose a novel graph abstraction that enables the direct derivation of tight bounds for monotonic graph algorithms, supporting effective pruning at both the vertex and partition levels. Comprehensive evaluations on six real-world datasets, including the 42.5-billion-edge ClueWeb graph, show that Gem significantly outperforms existing systems. It achieves up to 135.40× speedup over GridGraph and 12.58× over Wonderland in out-of-core settings, and also delivers substantial improvements in other modes: up to 10.41× over RisGraph in memory and 20.64× over CGgraph out-of-GPU memory.Keywords
Funding Information
- National Natural Science Foundation of China (62502193)
This publication has 79 references indexed in Scilit:
- A Survey on Efficient Graph Reachability Queries2025
- Accelerating Shortest Path Counting on Road Networks2025
- Towards Efficient Shortest Path Counting on Billion-Scale Graphs2023
- LOSC: A locality-optimized subgraph construction scheme for out-of-core graph processingJournal of Parallel and Distributed Computing, 2022
- Parallel graph coloring algorithms for distributed GPU environmentsParallel Computing, 2022
- Sphynx: A parallel multi-GPU graph partitioner for distributed-memory systemsParallel Computing, 2021
- CIC-PIM: Trading spare computing power for memory space in graph processingJournal of Parallel and Distributed Computing, 2021
- AKIN: A Streaming Graph Partitioning Algorithm for Distributed Graph Storage Systems2018
- Counterexample-Guided Abstraction Refinement2000
- Chapter 11 Network reliability1995