EUVIMEDEUVIMED entdecken
Crossref

Efficient GPU-Accelerated Subgraph Matching

Xibo Sun, Qiong Luo

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →