BishtRef
Articles Journals Publishers Authors Subjects Most Cited New Papers Year Stats Open Access
journal article Jun 17, 2025

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

Mehmet Aytimur ORCID Theodoros Chondrogiannis ORCID Michael Grossniklaus ORCID
Proceedings of the ACM on Management of Data Vol. 3 No. 3 pp. 1-26 · Association for Computing Machinery (ACM)
View at Publisher Save 10.1145/3725355
Abstract
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.
Topics

No keywords indexed for this article. Browse by subject →

References
56
[1]
Renzo Angles. 2018. The Property Graph Database Model. In Proceedings of the 12th Alberto Mendelzon International Workshop on Foundations of Data Management, Cali, Colombia, May 21--25, 2018 (CEUR Workshop Proceedings, Vol. 2100). CEUR-WS.org. https://ceur-ws.org/Vol-2100/paper26.pdf
[11]
Jeffrey Elman. 1998. Generalization, simple recurrent networks, and the emergence of structure. In Proceedings of the twentieth annual conference of the Cognitive Science Society. Mahwah, NJ: Lawrence Erlbaum Associates, 6.
[13]
Xiyang Feng, Guodong Jin, Ziyi Chen, Chang Liu, and Semih Salihoğlu. 2023. KÙZU graph database management system. In 13th Conference on Innovative Data Systems Research, CIDR. https://www.cidrdb.org/cidr2023/papers/p48-jin.pdf
[15]
Andrey Gubichev. 2015. Query Processing and Optimization in Graph Databases. Ph.D. Dissertation. Technische Universität München.
[17]
Long Short-Term Memory

Sepp Hochreiter, Jürgen Schmidhuber

Neural Computation 10.1162/neco.1997.9.8.1735
[19]
Andreas Kipf, Michael Freitag, Dimitri Vorona, Peter Boncz, Thomas Neumann, and Alfons Kemper. 2019. Estimating filtered group-by queries is hard: Deep learning to the rescue. In Proceedings of the InternationalWorkshop on Applied AI for Database Systems and Applications. https://drive.google.com/file/d/1Yt2w7_8UKFxsgcnWE8BjnFwhw509lyyY/view
[20]
Andreas Kipf, Thomas Kipf, Bernhard Radke, Viktor Leis, Peter A. Boncz, and Alfons Kemper. 2019. Learned Cardinalities: Estimating Correlated Joins with Deep Learning. In 9th Biennial Conference on Innovative Data Systems Research, CIDR. http://cidrdb.org/cidr2019/papers/p101-kipf-cidr19.pdf
[30]
M Muralikrishna and DJ DeWitt. 1988. Equidepth histograms for estimating selectivity factors for multi-dimensional queries. In Proc. of the 1988 ACM-SIGMOD Conference on the Management of Data. 28--36.
[39]
David E Rumelhart, James L McClelland, PDP Research Group, et al. 1986. Parallel distributed processing, volume 1: Explorations in the microstructure of cognition: Foundations. The MIT press.
[40]
The Graph Neural Network Model

F. Scarselli, M. Gori, Ah Chung Tsoi et al.

IEEE Transactions on Neural Networks 10.1109/tnn.2008.2005605
[48]
Ashish Vaswani Noam Shazeer Niki Parmar Jakob Uszkoreit Llion Jones Aidan N Gomez Łukasz Kaiser and Illia Polosukhin. 2017. Attention is all you need. (2017) 5998--6008. https://proceedings.neurips.cc/paper/2017/hash/3f5ee243547dee91fbd053c1c4a845aa-Abstract.html

Showing 50 of 56 references

Cited By
1
Enumerating Graph Pattern Matches with ML Oracles

Wenfei Fan, Yixuan Luo · 2026

Proceedings of the ACM on Managemen...
Metrics
1
Citations
56
References
Details
Published
Jun 17, 2025
Vol/Issue
3(3)
Pages
1-26
Authors
M
Mehmet Aytimur

University of Konstanz, Konstanz, Germany

T
Theodoros Chondrogiannis

University of Konstanz, Konstanz, Germany and Norwegian University of Science and Technology, Trondheim, Norway

M
Michael Grossniklaus

University of Konstanz, Konstanz, Germany and Thurgau Institute for Digitial Transformation, Kreuzlingen, Switzerland

Funding
Deutsche Forschungsgemeinschaft Award: GR 4497/5
Cite This Article
Mehmet Aytimur, Theodoros Chondrogiannis, Michael Grossniklaus (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
Related

You May Also Like

A Universal Question-Answering Platform for Knowledge Graphs

Reham Omar, Ishika Dhall · 2023

43 citations

FactorJoin: A New Cardinality Estimation Framework for Join Queries

Ziniu Wu, Parimarjan Negi · 2023

39 citations

RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search

Jianyang Gao, Cheng Long · 2024

39 citations

ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data

Liana Patel, Peter Kraft · 2024

37 citations

Efficient Sampling Approaches to Shapley Value Approximation

Jiayao Zhang, Qiheng Sun · 2023

34 citations