Efficient GPU-Accelerated Subgraph Matching
Proceedings of the ACM on Management of Data · 13.06.2023 · 1 (2) · 1-26
DOI: 10.1145/3589326 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 20.06.2023. Verfasst von Xibo Sun und 1 weiteren Autor:innen. Die Arbeit wurde bisher 30-mal zitiert (Crossref) und nennt 60 Literaturangaben. Gefördert von: RGC.
Abstract (Originalsprache)
Subgraph matching is a basic operation in graph analytics, finding all occurrences of a query graph Q in a data graph G. A common approach is to first filter out non-candidate vertices in G, and then order the vertices in Q to enumerate results. Recent work has started to utilize the GPU to accelerate subgraph matching. However, the effectiveness of current GPU-based filtering and ordering methods is limited, and the result enumeration often runs out of memory quickly. To address these problems, we propose EGSM, an efficient approach to GPU-based subgraph matching. Specifically, we design a data structure Cuckoo trie to support dynamic maintenance of candidates for filtering, and order query vertices based on estimated numbers of candidate vertices on the fly. Furthermore, we perform a hybrid breadth-first and depth-first search with memory management for result enumeration. Consequently, EGSM significantly outperforms the state-of-the-art GPU-accelerated algorithms, including GSI and CuTS.
Förderung
- RGC
Zitieren
APA
Sun, X., & Luo, Q. (2023). Efficient GPU-Accelerated Subgraph Matching. Proceedings of the ACM on Management of Data, 1(2), 1-26. https://doi.org/10.1145/3589326
Vancouver
Sun X, Luo Q. Efficient GPU-Accelerated Subgraph Matching. Proceedings of the ACM on Management of Data. 2023;1(2):1-26. doi:10.1145/3589326
BibTeX
@article{Sun2023,
author = {Sun, Xibo and Luo, Qiong},
title = {Efficient GPU-Accelerated Subgraph Matching},
journal = {Proceedings of the ACM on Management of Data},
year = {2023},
volume = {1},
number = {2},
pages = {1--26},
doi = {10.1145/3589326}
}
EUVIMED