PIE: Enabling Fast and Scalable Incremental Evolving Graph Analytics on Persistent Memory
Zhang, Yunmo Huang, Jiacheng Yin, Xizhe Qiu, Junqiao Xu, Hong Xue, Chun Jason
Zhang, Yunmo
Huang, Jiacheng
Yin, Xizhe
Qiu, Junqiao
Xu, Hong
Xue, Chun Jason
Supervisor
Department
Computer Science
Embargo End Date
Type
Conference proceeding
Date
2025
License
Language
English
Collections
Research Projects
Organizational Units
Journal Issue
Abstract
Graph processing is crucial for unstructured-data-driven applications in various domains. In recent years, there has been a growing need to perform real-time analytics on large-scale evolving graphs, which involves evaluating a graph query on a sequence of snapshots within a given time window. Some prior studies have explored utilizing persistent memory (PM) technologies, such as non-volatile memory, for efficient evolving graph analytics. However, the latest incremental processing designs fail to fully exploit the PM potential, suffering from severe read and write amplification during update ingestion and query evaluation. In this paper, we develop PIE, a PM-based incremental processing framework for fast and scalable evolving graph analytics. We first observe that leveraging CommonGraph, a recently proposed DRAM-based incremental approach that transforms costly deletions into additions, can significantly improve efficiency for evolving graph analytics in PM, although the direct adaptation introduces significant PM access inefficiencies. To enable PM-friendly incremental processing, PIE introduces a logical graph view abstraction that is detached from the physical storage to avoid extra PM writes, and a chunked neighbor index to reduce extensive PM reads during deletion transformation. Additionally, PIE prioritizes low-cost transformations when executing deletion-free incremental analytics. Furthermore, PIE incorporates two optimizations to balance key trade-offs in the proposed analytics on PM. Experimental results show that PIE significantly outperforms two state-of-the-art PM-based evolving graph systems, DGAP and XPGraph, as well as the direct PM adaptation of CommonGraph, achieving geometric mean speedups of 9.5 ×, 8.4 ×, and 10.9 × for update ingestion, and 18.1 ×, 20.4 × and 6.4 × for graph analytics, respectively.
Citation
Y. Zhang, J. Huang, X. Yin, J. Qiu, H. Xu, and C. J. Xue, “PIE: Enabling Fast and Scalable Incremental Evolving Graph Analytics on Persistent Memory,” Proceedings of the International Conference on Supercomputing, vol. Part of 213821, pp. 564–579, Aug. 2025, doi: 10.1145/3721145.3730419
Source
Proceedings of the 39th ACM International Conference on Supercomputing
Conference
39th ACM International Conference on Supercomputing, ICS 2025
Keywords
evolving graphs, incremental computing, persistent/non-volatile memory
Subjects
Source
39th ACM International Conference on Supercomputing, ICS 2025
Publisher
Association for Computing Machinery