cuMatch: A GPU-based Memory-Efficient Worst-case Optimal Join Processing Method for Subgraph Queries with Complex Patterns
Proceedings of the ACM on Management of Data · 17.06.2025 · 3 (3) · 1-28
DOI: 10.1145/3725398 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 18.06.2025. Verfasst von Sungwoo Park und 2 weiteren Autor:innen. Die Arbeit wurde bisher 6-mal zitiert (Crossref) und nennt 87 Literaturangaben.
Abstract (Originalsprache)
Subgraph queries are widely used but face significant challenges due to complex patterns such as negative and optional edges. While worst-case optimal joins have proven effective for subgraph queries with regular patterns, no method has been proposed that can process queries involving complex patterns in a single multi-way join. Existing CPU-based and GPU-based methods experience intermediate data explosion when processing complex patterns following regular patterns. In addition, GPU-based methods struggle with issues of wasted GPU memory and redundant computation. In this paper, we propose cuMatch, a GPU-based unified worst-case optimal join processing method for subgraph queries. It avoids intermediate data explosions by processing even complex pattern queries in a single multi-way join. It is also memory-efficient and fast, due to a new partitioning format, scheduling method, and task fusion technique. Extensive experiments demonstrate that cuMatch outperforms state-of-the-art methods by orders of magnitude, without out-of-memory errors.
Zitieren
APA
Park, S., Oh, S., & Kim, M. (2025). cuMatch: A GPU-based Memory-Efficient Worst-case Optimal Join Processing Method for Subgraph Queries with Complex Patterns. Proceedings of the ACM on Management of Data, 3(3), 1-28. https://doi.org/10.1145/3725398
Vancouver
Park S, Oh S, Kim M. cuMatch: A GPU-based Memory-Efficient Worst-case Optimal Join Processing Method for Subgraph Queries with Complex Patterns. Proceedings of the ACM on Management of Data. 2025;3(3):1-28. doi:10.1145/3725398
BibTeX
@article{Park2025,
author = {Park, Sungwoo and Oh, Seyeon and Kim, Min-Soo},
title = {cuMatch: A GPU-based Memory-Efficient Worst-case Optimal Join Processing Method for Subgraph Queries with Complex Patterns},
journal = {Proceedings of the ACM on Management of Data},
year = {2025},
volume = {3},
number = {3},
pages = {1--28},
doi = {10.1145/3725398}
}
EUVIMED