Circinus: Fast Redundancy-Reduced Subgraph Matching
Proceedings of the ACM on Management of Data · 26.05.2023 · 1 (1) · 1-26
DOI: 10.1145/3588692 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 30.05.2023. Verfasst von Tatiana Jin und 7 weiteren Autor:innen. Die Arbeit wurde bisher 35-mal zitiert (Crossref) und nennt 47 Literaturangaben.
Abstract (Originalsprache)
Subgraph matching is one of the most important problems in graph analytics. Many algorithms and systems have been proposed for subgraph matching. Most of these works follow Ullmann's backtracking approach as it is memory-efficient in handling an explosive number of intermediate matching results. However, they have largely overlooked an intrinsic problem of backtracking, namely repeated computation, which contributes to a large portion of the heavy computation in subgraph matching. This paper proposes a subgraph matching system, Circinus, which enables effective computation sharing by a new compression-based backtracking method. Our extensive experiments show that Circinus significantly reduces repeated computation, which transfers to up to several orders of magnitude performance improvement.
Zitieren
APA
Jin, T., Li, B., Li, Y., Zhou, Q., Ma, Q., Zhao, Y., Chen, H., & Cheng, J. (2023). Circinus: Fast Redundancy-Reduced Subgraph Matching. Proceedings of the ACM on Management of Data, 1(1), 1-26. https://doi.org/10.1145/3588692
Vancouver
Jin T, Li B, Li Y, Zhou Q, Ma Q, Zhao Y, et al. Circinus: Fast Redundancy-Reduced Subgraph Matching. Proceedings of the ACM on Management of Data. 2023;1(1):1-26. doi:10.1145/3588692
BibTeX
@article{Jin2023,
author = {Jin, Tatiana and Li, Boyang and Li, Yichao and Zhou, Qihui and Ma, Qianli and Zhao, Yunjian and Chen, Hongzhi and Cheng, James},
title = {Circinus: Fast Redundancy-Reduced Subgraph Matching},
journal = {Proceedings of the ACM on Management of Data},
year = {2023},
volume = {1},
number = {1},
pages = {1--26},
doi = {10.1145/3588692}
}
EUVIMED