Leveraging On-demand Processing to Co-optimize Scalability and Efficiency for Fully-external Graph Computation
ACM Transactions on Storage · 31.05.2025 · 21 (2) · 1-31
DOI: 10.1145/3701037 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Storage, online erschienen am 08.02.2025. Verfasst von Tsun-Yu Yang und 3 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 59 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: The Research Grants Council of Hong Kong SAR.
Abstract (Originalsprache)
Fully-external graph computation systems exhibit optimal scalability by computing the ever-growing, large-scale graph with a constant amount of memory on a single machine. In particular, they keep the entire massive graph data in storage and iteratively load parts of them into memory for computation. Nevertheless, despite the merit of optimal scalability, their unreasonably-low efficiency often makes them uncompetitive, and even unpractical, to the other types of graph computation systems. The key rationale is that most existing fully-external graph computation systems over-emphasize retrieving graph data from storage through sequential access. Although this principle achieves high storage bandwidth, it often causes reading excessive and irrelevant data, which can severely degrade their overall efficiency. Therefore, this work presents Seraph, a fully-external graph computation system that achieves optimal S calability while toward satisfactory E fficiency improvement. Particularly, inspired by the modern storage offering comparable sequential and random access speeds, Seraph adopts the principle of on-demand processing to access the necessary graph data for saving I/O while enjoying the decent speed in random access. On the basis of this principle, Seraph further devises three practical designs to bring excellent performance leap to fully-external graph computation: 1) the hybrid format to represent the graph data for striking a good balance between I/O amount and access locality, 2) the vertex passing to enable efficient vertex updates on top of hybrid format, and 3) the selective pre-computation to re-use the loaded data for I/O reduction. Our evaluations reveal that Seraph notably outperforms other state-of-the-art fully-external systems under all the evaluated billion-scale graphs and representative graph algorithms by up to two orders of magnitude.
Förderung
- The Research Grants Council of Hong Kong SAR
Zitieren
APA
Yang, T., Chen, Y., Liang, Y., & Yang, M. (2025). Leveraging On-demand Processing to Co-optimize Scalability and Efficiency for Fully-external Graph Computation. ACM Transactions on Storage, 21(2), 1-31. https://doi.org/10.1145/3701037
Vancouver
Yang T, Chen Y, Liang Y, Yang M. Leveraging On-demand Processing to Co-optimize Scalability and Efficiency for Fully-external Graph Computation. ACM Transactions on Storage. 2025;21(2):1-31. doi:10.1145/3701037
BibTeX
@article{Yang2025,
author = {Yang, Tsun-Yu and Chen, Yizou and Liang, Yuhong and Yang, Ming-Chang},
title = {Leveraging On-demand Processing to Co-optimize Scalability and Efficiency for Fully-external Graph Computation},
journal = {ACM Transactions on Storage},
year = {2025},
volume = {21},
number = {2},
pages = {1--31},
doi = {10.1145/3701037}
}
EUVIMED