{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T04:41:05Z","timestamp":1773895265533,"version":"3.50.1"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"9","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,5]]},"abstract":"<jats:p>\n            This paper presents PathCE, a path-centric cardinality estimation framework for subgraph matching. PathCE improves estimation accuracy by utilizing statistics from short graph queries. At its core is a novel data structure called the\n            <jats:italic toggle=\"yes\">path-centric summary graph<\/jats:italic>\n            (PSG), which captures short path query statistics from a data graph\n            <jats:italic toggle=\"yes\">G<\/jats:italic>\n            and represents them in a new graph\n            <jats:italic toggle=\"yes\">G<\/jats:italic>\n            . Given a graph query\n            <jats:italic toggle=\"yes\">Q<\/jats:italic>\n            and a PSG graph\n            <jats:italic toggle=\"yes\">G<\/jats:italic>\n            for G, PathCE decomposes\n            <jats:italic toggle=\"yes\">Q<\/jats:italic>\n            into a simpler query\n            <jats:italic toggle=\"yes\">G<\/jats:italic>\n            , where each edge in\n            <jats:italic toggle=\"yes\">G<\/jats:italic>\n            corresponds to a sub-path query in\n            <jats:italic toggle=\"yes\">Q<\/jats:italic>\n            with statistics included in\n            <jats:italic toggle=\"yes\">G<\/jats:italic>\n            . PathCE estimates the cardinality using\n            <jats:italic toggle=\"yes\">G<\/jats:italic>\n            and\n            <jats:italic toggle=\"yes\">G<\/jats:italic>\n            , requiring significantly fewer estimation iterations while ensuring that the estimate remains an upper bound on the true cardinality of\n            <jats:italic toggle=\"yes\">Q<\/jats:italic>\n            (\n            <jats:italic toggle=\"yes\">G<\/jats:italic>\n            ). It also includes PSGBuilder, a parallelly scalable algorithm that constructs PSG's for any given graph in linear time, efficiently scaling with the number of processors. Empirical results on real-world and synthetic datasets show that PathCE outperforms state-of-the-art baselines in accuracy, estimation latency, and summary construction efficiency.\n          <\/jats:p>","DOI":"10.14778\/3746405.3746428","type":"journal-article","created":{"date-parts":[[2025,9,3]],"date-time":"2025-09-03T17:06:20Z","timestamp":1756919180000},"page":"3063-3076","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Path-Centric Cardinality Estimation for Subgraph Matching"],"prefix":"10.14778","volume":"18","author":[{"given":"Zhengdong","family":"Wang","sequence":"first","affiliation":[{"name":"Shanghai Jiao Tong University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qiang","family":"Yin","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Longbin","family":"Lai","sequence":"additional","affiliation":[{"name":"Alibaba Group"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,9,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056105"},{"key":"e_1_2_1_2_1","unstructured":"Renzo Angles J\u00e1nos Benjamin Antal Alex Averbuch Altan Birler Peter Boncz M\u00e1rton B\u00far Orri Erling Andrey Gubichev Vlad Haprian Moritz Kaufmann Josep Llu\u00eds Larriba Pey Norbert Mart\u00ednez J\u00f3zsef Marton Marcus Paradies Minh-Duc Pham Arnau Prat-P\u00e9rez David P\u00fcroja Mirko Spasi\u0107 Benjamin A. Steer D\u00e1vid Szak\u00e1llas G\u00e1bor Sz\u00e1rnyas Jack Waudby Mingxi Wu and Yuchen Zhang. 2024. The LDBC Social Network Benchmark. arXiv:2001.02299 [cs.DB]"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.43"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319894"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3190508.3190545"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/3529337.3529339"},{"key":"e_1_2_1_7_1","unstructured":"Yannis Chronis Yawen Wang Yu Gan Sami Abu-El-Haija Chelsea Lin Carsten Binnig and Fatma \u00d6zcan. 2024. CardBench: A Benchmark for Learned Cardinality Estimation in Relational Databases. arXiv:2408.16170 [cs.DB]"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/3705829.3705834"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588907"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526057"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.46298\/dmtcs.3545"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3190657"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/3503585.3503586"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186728.3164145"},{"key":"e_1_2_1_16_1","volume-title":"Web Information Systems Engineering - WISE 2005 Workshops, Mike Dean, Yuanbo Guo, Woochun Jun, Roland Kaschek, Shonali Krishnaswamy, Zhengxiang Pan, and Quan Z","author":"Harris Stephen","unstructured":"Stephen Harris and Nigel Shadbolt. 2005. SPARQL Query Processing with Conventional Relational Database Systems. In Web Information Systems Engineering - WISE 2005 Workshops, Mike Dean, Yuanbo Guo, Woochun Jun, Roland Kaschek, Shonali Krishnaswamy, Zhengxiang Pan, and Quan Z. Sheng (Eds.). Springer Berlin, Heidelberg, 235\u2013244."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389741"},{"key":"e_1_2_1_18_1","volume-title":"Simplicity Done Right for Join Ordering. In 11th Biennial Conference on Innovative Data Systems Research (CIDR '21)","author":"Hertzschuch Axel","year":"2021","unstructured":"Axel Hertzschuch, Claudio Hartmann, Dirk Habich, and Wolfgang Lehner. 2021. Simplicity Done Right for Join Ordering. In 11th Biennial Conference on Innovative Data Systems Research (CIDR '21)."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3689209"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/169725.169708"},{"key":"e_1_2_1_21_1","volume-title":"Learned Cardinalities:Estimating Correlated Joins with Deep Learning. In 9th Biennial Conference on Innovative Data Systems Research (CIDR '19)","author":"Kipf Andreas","year":"2019","unstructured":"Andreas Kipf, Thomas Kipf, Bernhard Radke, Viktor Leis, Peter Boncz, and Alfons Kemper. 2019. Learned Cardinalities:Estimating Correlated Joins with Deep Learning. In 9th Biennial Conference on Innovative Data Systems Research (CIDR '19)."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(90)90192-K"},{"key":"e_1_2_1_23_1","volume-title":"GLogS: Interactive Graph Pattern Matching Query At Large Scale. In 2023 USENIX Annual Technical Conference (USENIX ATC 23)","author":"Lai Longbin","year":"2023","unstructured":"Longbin Lai, Yufan Yang, Zhibin Wang, Yuxuan Liu, Haotian Ma, Sijie Shen, Bingqing Lyu, Xiaoli Zhou, Wenyuan Yu, Zhengping Qian, Chen Tian, Sheng Zhong, Yeh-Ching Chung, and Jingren Zhou. 2023. GLogS: Interactive Graph Pattern Matching Query At Large Scale. In 2023 USENIX Annual Technical Conference (USENIX ATC 23). USENIX Association, Boston, MA, 53\u201369."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0480-7"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915235"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3698828"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3494124.3494127"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3722212.3724425"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3461837.3464516"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687738"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/3583140.3583164"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767868"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389702"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220097"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639299"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data","author":"Selinger P. Griffiths","unstructured":"P. Griffiths Selinger, M. M. Astrahan, D. D. Chamberlin, R. A. Lorie, and T. G. Price. 1979. Access path selection in a relational database management system. In Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data (Boston, Massachusetts) (SIGMOD '79). Association for Computing Machinery, New York, NY, USA, 23\u201334."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453899"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 2018 World Wide Web Conference (Lyon, France) (WWW '18). International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, CHE, 1043\u20131052","author":"Stefanoni Giorgio","unstructured":"Giorgio Stefanoni, Boris Motik, and Egor V. Kostylev. 2018. Estimating the Cardinality of Conjunctive Queries over RDF Data Using Graph Summarisation. In Proceedings of the 2018 World Wide Web Conference (Lyon, France) (WWW '18). International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, CHE, 1043\u20131052."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/3485450.3485459"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13278-010-0001-9"},{"key":"e_1_2_1_42_1","first-page":"6","article-title":"A General Cardinality Estimation Framework for Subgraph Matching in Property Graphs","volume":"35","author":"van Leeuwen Wilco","year":"2023","unstructured":"Wilco van Leeuwen, George Fletcher, and Nikolay Yakovets. 2023. A General Cardinality Estimation Framework for Subgraph Matching in Property Graphs. IEEE Trans. on Knowl. and Data Eng. 35, 6 (June 2023), 5485\u20135505.","journal-title":"IEEE Trans. on Knowl. and Data Eng."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824051"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/3485450.3485458"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461552"},{"key":"e_1_2_1_46_1","volume-title":"Cardinality Estimation Using Label Probability Propagation for Subgraph Matching in Property Graph Databases (EDBT '22)","author":"W\u00f6rteler Leonard","year":"2022","unstructured":"Leonard W\u00f6rteler, Moritz Renftle, Theodoros Chondrogiannis, and Michael Grossniklaus. 2022. Cardinality Estimation Using Label Probability Propagation for Subgraph Matching in Property Graph Databases (EDBT '22). OpenProceedings.org."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588721"},{"key":"e_1_2_1_48_1","unstructured":"Ziniu Wu Amir Shaikhha Rong Zhu Kai Zeng Yuxing Han and Jingren Zhou. 2021. BayesCard: Revitilizing Bayesian Frameworks for Cardinality Estimation. arXiv:2012.14743 [cs.DB]"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/3712221.3712231"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457289"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183739"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461539"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3746405.3746428","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T19:51:31Z","timestamp":1757015491000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3746405.3746428"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5]]},"references-count":52,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2025,5]]}},"alternative-id":["10.14778\/3746405.3746428"],"URL":"https:\/\/doi.org\/10.14778\/3746405.3746428","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2025,5]]},"assertion":[{"value":"2025-09-03","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}