{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,13]],"date-time":"2026-08-13T15:32:11Z","timestamp":1786635131147,"version":"build-2736575974"},"reference-count":76,"publisher":"Association for Computing Machinery (ACM)","issue":"2","funder":[{"name":"NSF-IIS","award":["2314527"],"award-info":[{"award-number":["2314527"]}]},{"name":"NSF-SHF","award":["2312195"],"award-info":[{"award-number":["2312195"]}]},{"name":"NSF-BSF","award":["2109922"],"award-info":[{"award-number":["2109922"]}]},{"DOI":"10.13039\/501100001711","name":"SNSF","doi-asserted-by":"crossref","award":["200021-231956"],"award-info":[{"award-number":["200021-231956"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,9]]},"abstract":"<jats:p>We study the classical evaluation problem for regular path queries: Given an edge-labeled graph and a regular path query, compute the set of pairs of vertices that are connected by paths that match the query.<\/jats:p>\n          <jats:p>The Product Graph (PG) is the established evaluation approach for regular path queries. PG first constructs the product automaton of the data graph and the query and then uses breadth-first search to find the accepting states reachable from each initial state in the product automaton. Its data complexity is O(|V|\u22c5|E|), where V and E are the sets of vertices and respectively edges in the data graph. This complexity cannot be improved by combinatorial algorithms.<\/jats:p>\n          <jats:p>\n            In this paper, we introduce OSPG, an output-sensitive refinement of PG, whose data complexity is O(|E|\n            <jats:sup>3\/2<\/jats:sup>\n            + min(OUT\u22c5\u221a|E|, |V|\u22c5|E|)), where OUT is the number of distinct vertex pairs in the query output. OSPG's complexity is at most that of PG and can be asymptotically smaller for small output and sparse input. The improvement of OSPG over PG is due to the unnecessary time wasted by PG in the breadth-first search phase, in case a few output pairs are eventually discovered. For queries without Kleene star, the complexity of OSPG can be further improved to O(|E| + |E|\u22c5\u221aOUT).\n          <\/jats:p>","DOI":"10.1145\/3725242","type":"journal-article","created":{"date-parts":[[2025,6,9]],"date-time":"2025-06-09T15:20:31Z","timestamp":1749482431000},"page":"1-20","source":"Crossref","is-referenced-by-count":3,"title":["Output-Sensitive Evaluation of Regular Path Queries"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3894-6494","authenticated-orcid":false,"given":"Mahmoud","family":"Abo Khamis","sequence":"first","affiliation":[{"name":"RelationalAI, Berkeley, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8155-8070","authenticated-orcid":false,"given":"Ahmet","family":"Kara","sequence":"additional","affiliation":[{"name":"OTH Regensburg, Regensburg, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4682-7068","authenticated-orcid":false,"given":"Dan","family":"Olteanu","sequence":"additional","affiliation":[{"name":"University of Zurich, Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4144-0868","authenticated-orcid":false,"given":"Dan","family":"Suciu","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","unstructured":"Amir Abboud Karl Bringmann Nick Fischer and Marvin K\u00fcnnemann. 2024. The Time Complexity of Fully Sparse Matrix Multiplication. In SODA. 4670--4703. doi:10.1137\/1.9781611977912.167","DOI":"10.1137\/1.9781611977912.167"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3426865"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902280"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","unstructured":"Mahmoud Abo Khamis Hung Q. Ngo and Dan Suciu. 2017. What Do Shannon-Type Inequalities Submodular Width and Disjunctive Datalog Have to Do with One Another?. In PODS. 429--444. doi:10.1145\/3034786.3056105","DOI":"10.1145\/3034786.3056105"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICDT.2017.4"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICDT.2024.25"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","unstructured":"Rasmus Resen Amossen and Rasmus Pagh. 2009. Faster Join-Projects and Sparse Matrix Multiplications. In ICDT. 121--126. doi:10.1145\/1514894.1514909","DOI":"10.1145\/1514894.1514909"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3104031"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","unstructured":"Pablo Barcel\u00f3 Baeza. 2013. Querying Graph Databases. In PODS. 175--188. doi:10.1145\/2463664.2465216","DOI":"10.1145\/2463664.2465216"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.JCSS.2019.08.006"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","unstructured":"Guillaume Bagan Arnaud Durand and Etienne Grandjean. 2007. On Acyclic Conjunctive Queries and Constant Delay Enumeration. In CSL. 208--222. doi:10.1007\/978--3--540--74915--8_18","DOI":"10.1007\/978--3--540--74915--8_18"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","unstructured":"Jean-Fran\u00e7ois Baget Meghyn Bienvenu Marie-Laure Mugnier and Micha\u00ebl Thomazo. 2017. Answering Conjunctive Regular Path Queries over Guarded Existential Rules. In IJCAI. 793--799. doi:10.24963\/IJCAI.2017\/110","DOI":"10.24963\/IJCAI.2017\/110"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556579"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2019.104"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2389241.2389250"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","unstructured":"Paul Beame Paraschos Koutris and Dan Suciu. 2014. Skew in Parallel Query Processing. In PODS. 212--223. doi:10.1145\/2594538.2594558","DOI":"10.1145\/2594538.2594558"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.MFCS.2019.58"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1613\/JAIR.4577"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","unstructured":"Meghyn Bienvenu and Micha\u00ebl Thomazo. 2016. On the Complexity of Evaluating Regular Path Queries over Linear Existential Rules. In RR. 1--17. doi:10.1007\/978--3--319--45276-0_1","DOI":"10.1007\/978--3--319--45276-0_1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00778-019-00558--9"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","unstructured":"Michele Borassi Pierluigi Crescenzi and Michel Habib. 2015. Into the Square: On the Complexity of Some Quadratictime Solvable Problems. In ICTCS. 51--67. doi:10.1016\/J.ENTCS.2016.03.005","DOI":"10.1016\/J.ENTCS.2016.03.005"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICDT.2021.20"},{"key":"e_1_2_1_23_1","unstructured":"Vicente Calisto Benjam\u00edn Farias Wim Martens Carlos Rojas and Domagoj Vrgoc. 2024. PathFinder Demo: Returning Paths in Graph Queries. In ISWC. https:\/\/ceur-ws.org\/Vol-3828\/paper34.pdf"},{"key":"e_1_2_1_24_1","volume-title":"Maurizio Lenzerini, and Moshe Y. Vardi.","author":"Calvanese Diego","year":"2000","unstructured":"Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Moshe Y. Vardi. 2000. Containment of Conjunctive Regular Path Queries with Inverse. In KR. 176--185."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/959060.959076"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3578517"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3531055"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.46298\/LMCS-19(4:15)2023"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICDT.2023.13"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","unstructured":"Shaleen Deep Xiao Hu and Paraschos Koutris. 2020. Fast Join Project Query Evaluation using Matrix Multiplication. In SIGMOD. 1213--1223. doi:10.1145\/3318464.3380607","DOI":"10.1145\/3318464.3380607"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICDT.2021.5"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3695838"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","unstructured":"Alin Deutsch Nadime Francis Alastair Green Keith Hare Bei Li Leonid Libkin Tobias Lindaaker Victor Marsault Wim Martens Jan Michels Filip Murlak Stefan Plantikow Petra Selmer Oskar van Rest Hannes Voigt Domagoj Vrgoc Mingxi Wu and Fred Zemke. 2022. Graph Pattern Matching in GQL and SQL\/PGQ. In SIGMOD. 2246--2258. doi:10.1145\/3514221.3526057","DOI":"10.1145\/3514221.3526057"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICDT.2020.9"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","unstructured":"Diego Figueira Adwait Godbole S. Krishna Wim Martens Matthias Niewerth and Tina Trautner. 2020. Containment of Simple Conjunctive Regular Path Queries. In KR. 371--380. doi:10.24963\/KR.2020\/38","DOI":"10.24963\/KR.2020\/38"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICDT.2023.15"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","unstructured":"Diego Figueira and Miguel Romero. 2023. Conjunctive Regular Path Queries under Injective Semantics. In PODS. 231--240. doi:10.1145\/3584372.3588664","DOI":"10.1145\/3584372.3588664"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICDT.2023.1"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3190657"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.JCSS.2013.01.008"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICDT.2019.15"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","unstructured":"Dirk Van Gucht Ryan Williams David P. Woodruff and Qin Zhang. 2015. The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication. In PODS. 199--212. doi:10.1145\/2745754.2745779","DOI":"10.1145\/2745754.2745779"},{"key":"e_1_2_1_43_1","unstructured":"Steve Harris and Andy Seaborne. 2013. SPARQL 1.1 Query Language. W3C Recommendation. http:\/\/www.w3.org\/TR\/sparql11-query\/."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3651599"},{"key":"e_1_2_1_45_1","unstructured":"Xiao Hu. 2025. Output-Optimal Algorithms for Join-Aggregate Queries. arXiv:2406.05536 https:\/\/arxiv.org\/abs\/2406.05536"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","unstructured":"Xiao Hu and Ke Yi. 2019. Instance and Output Optimal Parallel Algorithms for Acyclic Joins. In PODS. 450--463. doi:10.1145\/3294052.3319698","DOI":"10.1145\/3294052.3319698"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3311967"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICDT.2023.17"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.CSL.2023.29"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.46298\/LMCS-19(3:11)2023"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICDT.2023.11"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICDT.2025.20"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--1--4612--4400--4"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2850413"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2494529"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.46298\/LMCS-19(4:20)2023"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.14778\/3587136.3587151"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICDT.2018.19"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3371316.3371319"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3331446"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979122370X"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","unstructured":"Hung Q. Ngo. 2018. Worst-Case Optimal Join Algorithms: Techniques Results and Open Problems. In PODS. 111--124. doi:10.1145\/3196959.3196990","DOI":"10.1145\/3196959.3196990"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/2590989.2590991"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/2656335"},{"key":"e_1_2_1_65_1","unstructured":"Property Graph Query Language. 2021. PGQL 1.4 Specification. https:\/\/pgql-lang.org\/spec\/1.4\/."},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00224-016--9676--2"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514230"},{"key":"e_1_2_1_68_1","unstructured":"TigerGraph Team. 2021. TigerGraph Documentation -- version 3.1. https:\/\/docs.tigergraph.com\/."},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397250"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476306"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","unstructured":"Virginia Vassilevska Williams Yinzhan Xu Zixuan Xu and Renfei Zhou. 2024. New Bounds for Matrix Multiplication: from Alpha to Omega. In SODA. 3792--3835. doi:10.1137\/1.9781611977912.134","DOI":"10.1137\/1.9781611977912.134"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.5441\/002\/ICDT.2014.13"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1162\/DINT_A_00229"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/2206869.2206879"},{"key":"e_1_2_1_75_1","unstructured":"Mihalis Yannakakis. 1981. Algorithms for Acyclic Database Schemes. In VLDB. 82--94."},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","unstructured":"Hangdong Zhao Shaleen Deep and Paraschos Koutris. 2023. Space-Time Tradeoffs for Conjunctive Queries with Access Patterns. In PODS. 59--68. doi:10.1145\/3584372.3588675","DOI":"10.1145\/3584372.3588675"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725242","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T23:17:54Z","timestamp":1755904674000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725242"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,9]]},"references-count":76,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,9]]}},"alternative-id":["10.1145\/3725242"],"URL":"https:\/\/doi.org\/10.1145\/3725242","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,9]]}}}