Cheetah: Accelerating Dynamic Graph Mining with Grouping Updates
ACM Transactions on Architecture and Code Optimization · 30.06.2025 · 22 (2) · 1-26
DOI: 10.1145/3736173 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Architecture and Code Optimization, online erschienen am 02.07.2025. Verfasst von Yi Zhang und 10 weiteren Autor:innen. Die Arbeit wurde bisher 6-mal zitiert (Crossref) und nennt 53 Literaturangaben. Gefördert von: National Key Research and Development Program of China.
Abstract (Originalsprache)
Graph pattern mining is essential for deciphering complex networks. In the real world, graphs are dynamic and evolve over time, necessitating updates in mining patterns to reflect these changes. Traditional methods use fine-grained incremental computation to avoid full re-mining after each update, which improves speed but often overlooks potential gains from examining inter-update interactions holistically, thus missing out on overall efficiency improvements. In this article, we introduce Cheetah, a dynamic graph mining system that processes updates in a coarse-grained manner by leveraging exploration domains . These domains exploit the community structure of real-world graphs to uncover data reuse opportunities typically missed by existing approaches. Exploration domains, which encapsulate extensive portions of the graph relevant to updates, allow multiple updates to explore the same regions efficiently. Cheetah dynamically constructs these domains using a management module that identifies and maintains areas of redundancy as the graph changes. By grouping updates within these domains and employing a neighbor-centric expansion strategy, Cheetah minimizes redundant data accesses. Our evaluation of Cheetah across five real-world datasets shows it outperforms current leading systems by an average factor of 2.63×.
Förderung
- National Key Research and Development Program of China
Zitieren
APA
Zhang, Y., Yi, X., Huang, Y., Yuan, J., Gui, C., Chen, D., Zheng, L., Yue, J., Liao, X., Jin, H., & Xue, J. (2025). Cheetah: Accelerating Dynamic Graph Mining with Grouping Updates. ACM Transactions on Architecture and Code Optimization, 22(2), 1-26. https://doi.org/10.1145/3736173
Vancouver
Zhang Y, Yi X, Huang Y, Yuan J, Gui C, Chen D, et al. Cheetah: Accelerating Dynamic Graph Mining with Grouping Updates. ACM Transactions on Architecture and Code Optimization. 2025;22(2):1-26. doi:10.1145/3736173
BibTeX
@article{Zhang2025,
author = {Zhang, Yi and Yi, Xiaomeng and Huang, Yu and Yuan, Jingrui and Gui, Chuangyi and Chen, Dan and Zheng, Long and Yue, Jianhui and Liao, Xiaofei and Jin, Hai and Xue, Jingling},
title = {Cheetah: Accelerating Dynamic Graph Mining with Grouping Updates},
journal = {ACM Transactions on Architecture and Code Optimization},
year = {2025},
volume = {22},
number = {2},
pages = {1--26},
doi = {10.1145/3736173}
}
EUVIMED