{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T00:28:24Z","timestamp":1778113704341,"version":"3.51.4"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,5,10]],"date-time":"2024-05-10T00:00:00Z","timestamp":1715299200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100006374","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-18-CE40-0031"],"award-info":[{"award-number":["ANR-18-CE40-0031"]}],"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":[[2024,5,10]]},"abstract":"<jats:p>We consider the Distinct Shortest Walks problem. Given two vertices s and t of a graph database D and a regular path query, we want to enumerate all walks of minimal length from s to t that carry a label that conforms to the query. Usual theoretical solutions turn out to be inefficient when applied to graph models that are closer to real-life systems, in particular because edges may carry multiple labels. Indeed, known algorithms may repeat the same answer exponentially many times. We propose an efficient algorithm for graph databases with multiple labels. The preprocessing runs in O(DxA) and the delay between two consecutive outputs is in O(\u03bbxA), where A is a nondeterministic automaton representing the query and L is the minimal length. The algorithm can handle epsilon-transitions in A or queries given as regular expressions at no additional cost.<\/jats:p>","DOI":"10.1145\/3651601","type":"journal-article","created":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T08:32:13Z","timestamp":1715675533000},"page":"1-22","source":"Crossref","is-referenced-by-count":4,"title":["Distinct Shortest Walk Enumeration for RPQs"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3041-7013","authenticated-orcid":false,"given":"Claire","family":"David","sequence":"first","affiliation":[{"name":"LIGM, Universit\u00e9 Gustave Eiffel, CNRS, Champs-sur-Marne, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-4531-7435","authenticated-orcid":false,"given":"Nadime","family":"Francis","sequence":"additional","affiliation":[{"name":"LIGM, Universit\u00e9 Gustave Eiffel, CNRS, Champs-sur-Marne, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2325-6004","authenticated-orcid":false,"given":"Victor","family":"Marsault","sequence":"additional","affiliation":[{"name":"LIGM, Universit\u00e9 Gustave Eiffel, CNRS, Champs-sur-Marne, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,5,14]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.03.018"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2023.8"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Renzo Angles Marcelo Arenas Pablo Barcel\u00f3 Peter A. Boncz George H. L. Fletcher Claudio Gutierrez Tobias Lindaaker Marcus Paradies Stefan Plantikow Juan F. Sequeda Oskar van Rest and Hannes Voigt. 2018. G-CORE: A Core for Future Graph Query Languages. In SIGMOD. ACM 1421--1432.","DOI":"10.1145\/3183713.3190654"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3104031"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.56"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--642-02927--1_16"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90287-4"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/38713.38749"},{"key":"e_1_2_1_9_1","volume-title":"Lee","author":"Deutsch Alin","year":"2019","unstructured":"Alin Deutsch, Yu Xu, Mingxi Wu, and Victor E. Lee. 2019. TigerGraph: A Native MPP Graph Database. http:\/\/arxiv.org\/abs\/1901.08248 Preprint hrefhttps:\/\/arxiv.org\/abs\/1901.08248arXiv:1901.08249."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588334"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2306.02194"},{"key":"e_1_2_1_12_1","unstructured":"International Organization for Standardization. 2024. GQL. Standard under development ISO\/IEC DIS 39075. https:\/\/www.iso.org\/standard\/76120.html To appear."},{"key":"e_1_2_1_13_1","volume-title":"GPC: A Pattern Calculus for Property Graphs. In PODS'23","author":"Francis Nadime","year":"2023","unstructured":"Nadime Francis, Am\u00e9lie Gheerbrant, Paolo Guagliardo, Leonid Libkin, Victor Marsault, Wim Martens, Filip Murlak, Liat Peterfreund, Alexandra Rogova, and Domagoj Vrgo?. 2023. GPC: A Pattern Calculus for Property Graphs. In PODS'23. https:\/\/arxiv.org\/abs\/2210.16580"},{"key":"e_1_2_1_14_1","unstructured":"Nadime Francis and Victor Marsault. 2023. Enumerating regular languages in radix order : Revisiting the Ackerman-Shallit algorithm. hrefhttps:\/\/arxiv.org\/abs\/2310.13309ArXiv:2310.13309."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","unstructured":"M.L. Fredman and R.E. Tarjan. 1984. Fibonacci Heaps And Their Uses In Improved Network Optimization Algorithms. (1984) 338--346. https:\/\/doi.org\/10.1109\/SFCS.1984.715934","DOI":"10.1109\/SFCS.1984.715934"},{"key":"e_1_2_1_16_1","unstructured":"Property Graph Query Language. 2021. PGQL 2.0 Specification. https:\/\/pgql-lang.org\/spec\/2.0\/"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3587136.3587151"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2018.19"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/128749.128755"},{"key":"e_1_2_1_20_1","unstructured":"Tina Popp. 2022. Evaluation and Enumeration of Regular Simple Path and Trail Queries. Ph. D. Dissertation. Bayreuth. https:\/\/epub.uni-bayreuth.de\/6606\/"},{"key":"e_1_2_1_21_1","volume-title":"Enumeration Complexity: Incremental Time, Delay and Space. Universit\u00e9 de Versailles -- Saint-Quentin-en-Yvelines. Habilitation thesis.","author":"Strozecki Yann","year":"2021","unstructured":"Yann Strozecki. 2021. Enumeration Complexity: Incremental Time, Delay and Space. Universit\u00e9 de Versailles -- Saint-Quentin-en-Yvelines. Habilitation thesis."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/363347.363387"},{"key":"e_1_2_1_23_1","unstructured":"TigerGraph. 2023. GSQL Language Reference (version 3.9). https:\/\/docs.tigergraph.com\/gsql-ref\/3.9\/intro\/"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651601","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3651601","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T21:38:51Z","timestamp":1755898731000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651601"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,10]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,5,10]]}},"alternative-id":["10.1145\/3651601"],"URL":"https:\/\/doi.org\/10.1145\/3651601","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,10]]}}}