EUVIMEDEUVIMED entdecken
Crossref

SPACE: Cardinality Estimation for Path Queries Using Cardinality-Aware Sequence-based Learning

Mehmet Aytimur, Theodoros Chondrogiannis, Michael Grossniklaus

Proceedings of the ACM on Management of Data · 17.06.2025 · 3 (3) · 1-26

DOI: 10.1145/3725355 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 18.06.2025. Verfasst von Mehmet Aytimur und 2 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 56 Literaturangaben. Gefördert von: Deutsche Forschungsgemeinschaft.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Cardinality estimation is a central task of cost-based database query optimization. Accurate estimates enable optimizers to identify and avoid expensive plans requiring large intermediate results. While cardinality estimation has been studied extensively in relational databases, research in the setting of graph databases has been more scarce. Furthermore, recent studies have shown that machine-learning-based methods can be utilized for cardinality estimation in both relational and graph databases. In this paper, we focus on the problem of estimating the cardinality of path patterns in graph databases, and we propose the Sequence-based Path Pattern Cardinality Estimator (SPACE). Our approach treats path patterns as sequences of node labels and edge types and assign similar cardinalities to path patterns with similar node and edge order. SPACE uses a dual approach: it encodes the sequence of nodes and edges to capture structural characteristics of the path pattern, while also incorporating a cardinality-based encoding to integrate cardinality information throughout learning. In a comprehensive experimental evaluation, we show that our method outperforms the state of the art in terms of both accuracy ( Q -error) and training time.

Förderung

  • Deutsche Forschungsgemeinschaft

Zitieren

APA

Aytimur, M., Chondrogiannis, T., & Grossniklaus, M. (2025). SPACE: Cardinality Estimation for Path Queries Using Cardinality-Aware Sequence-based Learning. Proceedings of the ACM on Management of Data, 3(3), 1-26. https://doi.org/10.1145/3725355

Vancouver

Aytimur M, Chondrogiannis T, Grossniklaus M. SPACE: Cardinality Estimation for Path Queries Using Cardinality-Aware Sequence-based Learning. Proceedings of the ACM on Management of Data. 2025;3(3):1-26. doi:10.1145/3725355

BibTeX
@article{Aytimur2025,
  author = {Aytimur, Mehmet and Chondrogiannis, Theodoros and Grossniklaus, Michael},
  title = {SPACE: Cardinality Estimation for Path Queries Using Cardinality-Aware Sequence-based Learning},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2025},
  volume = {3},
  number = {3},
  pages = {1--26},
  doi = {10.1145/3725355}
}
Kostenlos starten →