GuP: Fast Subgraph Matching by Guard-based Pruning
Proceedings of the ACM on Management of Data · 13.06.2023 · 1 (2) · 1-26
DOI: 10.1145/3589312 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 20.06.2023. Verfasst von Junya Arai und 2 weiteren Autor:innen. Die Arbeit wurde bisher 48-mal zitiert (Crossref) und nennt 40 Literaturangaben.
Abstract (Originalsprache)
Subgraph matching, which finds subgraphs isomorphic to a query, is crucial for information retrieval from data represented as a graph. To avoid redundant explorations in the data, existing methods restrict the search space by extracting candidate vertices and edges that may constitute isomorphic subgraphs. However, expensive computation is still required because candidate vertices induce many non-isomorphic subgraphs. In this paper, we propose GuP, a subgraph matching algorithm with pruning based on guards. A guard represents a pattern of intermediate search states that never lead to isomorphic subgraphs. By attaching a guard to each candidate vertex and edge, GuP adaptively filters out unnecessary candidates depending on the search state at each step. The experimental results show that GuP effectively reduces the search space and can answer difficult queries that state-of-the-art methods cannot answer within a practical time frame.
Zitieren
APA
Arai, J., Fujiwara, Y., & Onizuka, M. (2023). GuP: Fast Subgraph Matching by Guard-based Pruning. Proceedings of the ACM on Management of Data, 1(2), 1-26. https://doi.org/10.1145/3589312
Vancouver
Arai J, Fujiwara Y, Onizuka M. GuP: Fast Subgraph Matching by Guard-based Pruning. Proceedings of the ACM on Management of Data. 2023;1(2):1-26. doi:10.1145/3589312
BibTeX
@article{Arai2023,
author = {Arai, Junya and Fujiwara, Yasuhiro and Onizuka, Makoto},
title = {GuP: Fast Subgraph Matching by Guard-based Pruning},
journal = {Proceedings of the ACM on Management of Data},
year = {2023},
volume = {1},
number = {2},
pages = {1--26},
doi = {10.1145/3589312}
}
EUVIMED