EUVIMEDEUVIMED entdecken
Crossref

Cardinality Estimation of Subgraph Matching: A Filtering-Sampling Approach

Wonseok Shin, Siwoo Song, Kunsoo Park, Wook-Shin Han

Proceedings of the VLDB Endowment · 2024-03 · 17 (7) · 1697-1709

DOI: 10.14778/3654621.3654635 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 30.05.2024. Verfasst von Wonseok Shin und 3 weiteren Autor:innen. Die Arbeit wurde bisher 15-mal zitiert (Crossref) und nennt 52 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Subgraph counting is a fundamental problem in understanding and analyzing graph structured data, yet computationally challenging. This calls for an accurate and efficient algorithm for Subgraph Cardinality Estimation, which is to estimate the number of all isomorphic embeddings of a query graph in a data graph. We present FaST est , a novel algorithm that combines (1) a powerful filtering technique to significantly reduce the sample space, (2) an adaptive tree sampling algorithm for accurate and efficient estimation, and (3) a worst-case optimal stratified graph sampling algorithm for hard instances. Extensive experiments on real-world datasets show that FaST est outperforms state-of-the-art sampling-based methods by up to two orders of magnitude and GNN-based methods by up to three orders of magnitude in terms of accuracy.

Zitieren

APA

Shin, W., Song, S., Park, K., & Han, W. (2024). Cardinality Estimation of Subgraph Matching: A Filtering-Sampling Approach. Proceedings of the VLDB Endowment, 17(7), 1697-1709. https://doi.org/10.14778/3654621.3654635

Vancouver

Shin W, Song S, Park K, Han W. Cardinality Estimation of Subgraph Matching: A Filtering-Sampling Approach. Proceedings of the VLDB Endowment. 2024;17(7):1697-1709. doi:10.14778/3654621.3654635

BibTeX
@article{Shin2024,
  author = {Shin, Wonseok and Song, Siwoo and Park, Kunsoo and Han, Wook-Shin},
  title = {Cardinality Estimation of Subgraph Matching: A Filtering-Sampling Approach},
  journal = {Proceedings of the VLDB Endowment},
  year = {2024},
  volume = {17},
  number = {7},
  pages = {1697--1709},
  doi = {10.14778/3654621.3654635}
}
Kostenlos starten →