{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T08:59:14Z","timestamp":1775638754982,"version":"3.50.1"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"DOI":"10.13039\/501100006374","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["GR 4497\/5"],"award-info":[{"award-number":["GR 4497\/5"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,17]]},"abstract":"<jats:p>\n                    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\n                    <jats:italic toggle=\"yes\">Sequence-based Path Pattern Cardinality Estimator<\/jats:italic>\n                    (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 (\n                    <jats:italic toggle=\"yes\">Q<\/jats:italic>\n                    -error) and training time.\n                  <\/jats:p>","DOI":"10.1145\/3725355","type":"journal-article","created":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:22:29Z","timestamp":1750281749000},"page":"1-26","source":"Crossref","is-referenced-by-count":2,"title":["SPACE: Cardinality Estimation for Path Queries Using Cardinality-Aware Sequence-based Learning"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1029-0473","authenticated-orcid":false,"given":"Mehmet","family":"Aytimur","sequence":"first","affiliation":[{"name":"University of Konstanz, Konstanz, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9623-9133","authenticated-orcid":false,"given":"Theodoros","family":"Chondrogiannis","sequence":"additional","affiliation":[{"name":"University of Konstanz, Konstanz, Germany and Norwegian University of Science and Technology, Trondheim, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1609-2221","authenticated-orcid":false,"given":"Michael","family":"Grossniklaus","sequence":"additional","affiliation":[{"name":"University of Konstanz, Konstanz, Germany and Thurgau Institute for Digitial Transformation, Kreuzlingen, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,18]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Proceedings of the 12th Alberto Mendelzon International Workshop on Foundations of Data Management, Cali, Colombia, May 21--25, 2018 (CEUR Workshop Proceedings","volume":"26","author":"Angles Renzo","year":"2018","unstructured":"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"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.3906\/elk-1806--96"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2020.113762"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639309"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3461477"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/3149193.3149196"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/3529337.3529339"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.3115\/v1\/d14--1179"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.48786\/EDBT.2022.07"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/3329772.3329780"},{"key":"e_1_2_2_11_1","volume-title":"Proceedings of the twentieth annual conference of the Cognitive Science Society. Mahwah, NJ: Lawrence Erlbaum Associates, 6.","author":"Elman Jeffrey","year":"1998","unstructured":"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."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742786"},{"key":"e_1_2_2_13_1","volume-title":"13th Conference on Innovative Data Systems Research, CIDR. https:\/\/www.cidrdb.org\/cidr2023\/papers\/p48-jin.pdf","author":"Feng Xiyang","year":"2023","unstructured":"Xiyang Feng, Guodong Jin, Ziyi Chen, Chang Liu, and Semih Saliho\u011flu. 2023. K\u00d9ZU graph database management system. In 13th Conference on Innovative Data Systems Research, CIDR. https:\/\/www.cidrdb.org\/cidr2023\/papers\/p48-jin.pdf"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3190657"},{"key":"e_1_2_2_15_1","unstructured":"Andrey Gubichev. 2015. Query Processing and Optimization in Graph Databases. Ph.D. Dissertation. Technische Universit\u00e4t M\u00fcnchen."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/3503585.3503586"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1162\/neco.1997.9.8.1735"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/169725.169708"},{"key":"e_1_2_2_19_1","volume-title":"Proceedings of the InternationalWorkshop on Applied AI for Database Systems and Applications. https:\/\/drive.google.com\/file\/d\/1Yt2w7_8UKFxsgcnWE8BjnFwhw509lyyY\/view","author":"Kipf Andreas","year":"2019","unstructured":"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"},{"key":"e_1_2_2_20_1","volume-title":"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","author":"Kipf Andreas","year":"2019","unstructured":"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"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196909"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233341"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/645924.671200"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516455"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2899413"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342643"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687738"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--540--76298-0_58"},{"key":"e_1_2_2_30_1","volume-title":"Proc. of the 1988 ACM-SIGMOD Conference on the Management of Data. 28--36","author":"Muralikrishna M","year":"1988","unstructured":"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."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/3583140.3583164"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767868"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453927"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389702"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1567274.1567278"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/235968.233342"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/3636218.3636229"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--319--46523--4_30"},{"key":"e_1_2_2_39_1","volume-title":"Explorations in the microstructure of cognition: Foundations","author":"Rumelhart David E","year":"1986","unstructured":"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."},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNN.2008.2005605"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639299"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/3436905.3436907"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1328854.1328856"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178876.3186003"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367578"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.WEBSEM.2008.06.001"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505756"},{"key":"e_1_2_2_48_1","unstructured":"Ashish Vaswani Noam Shazeer Niki Parmar Jakob Uszkoreit Llion Jones Aidan N Gomez \u0141ukasz Kaiser and Illia Polosukhin. 2017. Attention is all you need. (2017) 5998--6008. https:\/\/proceedings.neurips.cc\/paper\/2017\/hash\/3f5ee243547dee91fbd053c1c4a845aa-Abstract.html"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824051"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1162\/TACL_A_00360"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.48786\/EDBT.2022.16"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3177850"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.5441\/002\/EDBT.2018.55"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/3368289.3368294"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.24963\/IJCAI.2019\/594"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457289"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725355","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T19:00:29Z","timestamp":1774983629000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725355"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,17]]},"references-count":56,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6,17]]}},"alternative-id":["10.1145\/3725355"],"URL":"https:\/\/doi.org\/10.1145\/3725355","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,17]]}}}