EUVIMEDEUVIMED entdecken
Crossref

cuMatch: A GPU-based Memory-Efficient Worst-case Optimal Join Processing Method for Subgraph Queries with Complex Patterns

Sungwoo Park, Seyeon Oh, Min-Soo Kim

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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