{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T01:43:09Z","timestamp":1787017389554,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":56,"publisher":"ACM","license":[{"start":{"date-parts":[[2025,4,22]],"date-time":"2025-04-22T00:00:00Z","timestamp":1745280000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/https:\/\/doi.org\/10.13039\/501100004837","name":"Ministerio de Ciencia e Innovaci\u00f3n","doi-asserted-by":"publisher","award":["PID2020-114635RB-I00"],"award-info":[{"award-number":["PID2020-114635RB-I00"]}],"id":[{"id":"10.13039\/https:\/\/doi.org\/10.13039\/501100004837","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/https:\/\/doi.org\/10.13039\/501100020884","name":"Agencia Nacional de Investigaci\u00f3n y Desarrollo","doi-asserted-by":"publisher","award":["Millennium Science Initiative Program Code ICN17_002"],"award-info":[{"award-number":["Millennium Science Initiative Program Code ICN17_002"]}],"id":[{"id":"10.13039\/https:\/\/doi.org\/10.13039\/501100020884","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/https:\/\/doi.org\/10.13039\/501100020884","name":"Agencia Nacional de Investigaci\u00f3n y Desarrollo","doi-asserted-by":"publisher","award":["Fondecyt grant 11220545"],"award-info":[{"award-number":["Fondecyt grant 11220545"]}],"id":[{"id":"10.13039\/https:\/\/doi.org\/10.13039\/501100020884","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/https:\/\/doi.org\/10.13039\/501100020884","name":"Agencia Nacional de Investigaci\u00f3n y Desarrollo","doi-asserted-by":"publisher","award":["Fondecyt grant 1221926"],"award-info":[{"award-number":["Fondecyt grant 1221926"]}],"id":[{"id":"10.13039\/https:\/\/doi.org\/10.13039\/501100020884","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/https:\/\/doi.org\/10.13039\/501100020884","name":"Agencia Nacional de Investigaci\u00f3n y Desarrollo","doi-asserted-by":"publisher","award":["Fondecyt grant 1-230755"],"award-info":[{"award-number":["Fondecyt grant 1-230755"]}],"id":[{"id":"10.13039\/https:\/\/doi.org\/10.13039\/501100020884","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/https:\/\/doi.org\/10.13039\/501100020884","name":"Agencia Nacional de Investigaci\u00f3n y Desarrollo","doi-asserted-by":"publisher","award":["Fondecyt grant 1221799"],"award-info":[{"award-number":["Fondecyt grant 1221799"]}],"id":[{"id":"10.13039\/https:\/\/doi.org\/10.13039\/501100020884","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/https:\/\/doi.org\/10.13039\/501100020884","name":"Agencia Nacional de Investigaci\u00f3n y Desarrollo","doi-asserted-by":"publisher","award":["PFCHA \/ Doctorado Nacional \/ 2021-21211768"],"award-info":[{"award-number":["PFCHA \/ Doctorado Nacional \/ 2021-21211768"]}],"id":[{"id":"10.13039\/https:\/\/doi.org\/10.13039\/501100020884","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Ministerio de Ciencia e Innovaci\u00f3n y Fondos NextGenerationEU","award":["TED2021-129245B-C21"],"award-info":[{"award-number":["TED2021-129245B-C21"]}]},{"name":"FEDER Galicia","award":["ED431G 2023\/01"],"award-info":[{"award-number":["ED431G 2023\/01"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,4,22]]},"DOI":"10.1145\/3696410.3714695","type":"proceedings-article","created":{"date-parts":[[2025,4,22]],"date-time":"2025-04-22T18:57:28Z","timestamp":1745348248000},"page":"59-71","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Worst-Case-Optimal Joins on Graphs with Topological Relations"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3962-6495","authenticated-orcid":false,"given":"Jos\u00e9","family":"Fuentes-Sep\u00falveda","sequence":"first","affiliation":[{"name":"Universidad de Concepci\u00f3n, Concepci\u00f3n, Chile and Millennium Institute for Foundational Research on Data, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1216-2176","authenticated-orcid":false,"given":"Adri\u00e1n","family":"G\u00f3mez-Brand\u00f3n","sequence":"additional","affiliation":[{"name":"Universidade da Coru\u00f1a, A Coru\u00f1a, Spain, Millennium Institute for Foundational Research on Data, Santiago, Chile, and Centro de Investigaci\u00f3n TIC, A Coru\u00f1a, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9482-1982","authenticated-orcid":false,"given":"Aidan","family":"Hogan","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Chile, Santiago, Chile and Millennium Institute for Foundational Research on Data, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-3288-9590","authenticated-orcid":false,"given":"Ayleen","family":"Irribarra-Cort\u00e9s","sequence":"additional","affiliation":[{"name":"Universidad de Concepci\u00f3n, Concepci\u00f3n, Chile and Millennium Institute for Foundational Research on Data, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2286-741X","authenticated-orcid":false,"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Chile, Santiago, Chile and Millennium Institute for Foundational Research on Data, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2186-0312","authenticated-orcid":false,"given":"Juan","family":"Reutter","sequence":"additional","affiliation":[{"name":"Pontificia Universidad Cat\u00f3lica de Chile, Santiago, Chile and Millennium Institute for Foundational Research on Data, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,4,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3129246"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3104031"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1322432.1322433"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3644824"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457256"},{"key":"e_1_3_2_1_6_1","volume-title":"Proc. 36th European Workshop on Computational Geometry (EuroCG). article 53","author":"Arseneva Elena","unstructured":"Elena Arseneva, Linda Kleist, Boris Klemz, Maarten L\u00f6ffler, Andr\u00e9 Schulz, Birgit Vogtenhuber, and Alexander Wolff. [n. d.]. Representing Graphs by Polygons with Edge Contacts in 3D. In Proc. 36th European Workshop on Computational Geometry (EuroCG). article 53."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/110859440"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2013.10.003"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.3233\/SW-2012-0065"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-19433-7_4"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1013367.1013381"},{"key":"e_1_3_2_1_12_1","volume-title":"Proc. 24th International Conference on Database Theory (ICDT). 19:1--19:20","author":"Casel Katrin","unstructured":"Katrin Casel and Markus L. Schmid. 2021. Fine-grained complexity of regular path queries. In Proc. 24th International Conference on Database Theory (ICDT). 19:1--19:20."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2014.06.002"},{"key":"e_1_3_2_1_15_1","volume-title":"Proc. 26th International Conference on Database Theory (ICDT","author":"Cucumides Tamara","year":"2023","unstructured":"Tamara Cucumides, Juan Reutter, and Domagoj Vrgoc. 2023. Size Bounds and Algorithms for Conjunctive Regular Path Queries. In Proc. 26th International Conference on Database Theory (ICDT 2023)."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11224-016-0853-3"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3459637.3482023"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1080\/02693799108927841"},{"key":"e_1_3_2_1_19_1","volume-title":"Networked Knowledge-Networked Media: Integrating Knowledge Management, New Media Technologies and Semantic Systems","author":"Erling Orri","unstructured":"Orri Erling and Ivan Mikhailov. 2009. RDF Support in the Virtuoso DBMS. In Networked Knowledge-Networked Media: Integrating Knowledge Management, New Media Technologies and Semantic Systems. Springer, 7--24."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376737"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.isprsjprs.2003.09.003"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07959-2_28"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2220357.2220363"},{"key":"e_1_3_2_1_24_1","volume-title":"Proc. 14th International Joint Conference on Artificial Intelligence (IJCAI), part 1. 901--907","author":"Grigni Michelangelo","year":"1995","unstructured":"Michelangelo Grigni, Dimitris Papadias, and Christos Papadimitriou. 1995. Topological inference. In Proc. 14th International Joint Conference on Artificial Intelligence (IJCAI), part 1. 901--907."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1111\/TGIS.12196"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.ARTINT.2012"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447772"},{"key":"e_1_3_2_1_28_1","volume-title":"Proc. International Semantic Web Conference (ISWC). 258--275","author":"Hogan Aidan","year":"2019","unstructured":"Aidan Hogan, Cristian Riveros, Carlos Rojas, and Adrian Soto. 2019. A worstcase optimal join algorithm for SPARQL. In Proc. International Semantic Web Conference (ISWC). 258--275."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2424321.2424323"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.2991\/IJCIS.10.1.96"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13486-9_29"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35176-1_19"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.3233\/SW-140134"},{"key":"e_1_3_2_1_34_1","volume-title":"Proc. 27th International Conference on Very Large Databases (VLDB). 425--436","author":"Li Quanzhong","year":"2001","unstructured":"Quanzhong Li and Bongki Moon. 2001. Indexing and Querying XML Data for Regular Path Expressions. In Proc. 27th International Conference on Very Large Databases (VLDB). 425--436."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367064.1367072"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-00668-6_23"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3446980"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/3554821.3554894"},{"key":"e_1_3_2_1_39_1","volume-title":"Tables. In Proc. 16th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). 37--42","author":"Munro J. Ian","year":"1996","unstructured":"J. Ian Munro. 1996. Tables. In Proc. 16th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). 37--42."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.03.005"},{"key":"e_1_3_2_1_41_1","volume-title":"Compact Data Structures -- A practical approach","author":"Navarro Gonzalo","unstructured":"Gonzalo Navarro. 2016. Compact Data Structures -- A practical approach. Cambridge University Press."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601073"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3180143"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764947.2764948"},{"key":"e_1_3_2_1_45_1","volume-title":"PostGIS in action","author":"Obe Regina","unstructured":"Regina Obe and Leo S Hsu. 2021. PostGIS in action. Simon and Schuster."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1597"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3207677.3277981"},{"key":"e_1_3_2_1_48_1","volume-title":"Proc. 3rd International Conference on Knowledge Representation and Reasoning. 165--176","author":"Randell D. A.","unstructured":"D. A. Randell, Z Cui, and A. G. Cohn. 1992. A spatial logic based on regions and connection. In Proc. 3rd International Conference on Knowledge Representation and Reasoning. 165--176."},{"key":"e_1_3_2_1_49_1","volume-title":"Qualitative Spatial Reasoning with Topological Information","author":"Renz Jochen","unstructured":"Jochen Renz. 2002. The Region Connection Calculus. In Qualitative Spatial Reasoning with Topological Information. Springer, 41--50."},{"key":"e_1_3_2_1_50_1","volume-title":"Spatial databases - with applications to GIS","author":"Rigaux Philippe","unstructured":"Philippe Rigaux, Michel Scholl, and Agn\u00e8s Voisard. 2002. Spatial databases - with applications to GIS. Elsevier."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.3233\/SW-2011-0052"},{"key":"e_1_3_2_1_52_1","volume-title":"Linked Data Management","author":"Thompson Bryan B.","unstructured":"Bryan B. Thompson, Michael Personick, and Martyn Cutcher. 2014. Linked Data Management. Chapman and Hall\/CRC, Chapter The Bigdata\u00ae RDF Graph Database, 193--237."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.14778\/3554821.3554878"},{"key":"e_1_3_2_1_54_1","volume-title":"Proc. International Conference on Database Theory (ICDT). 96--106","author":"Veldhuizen Todd L.","year":"2014","unstructured":"Todd L. Veldhuizen. 2014. Triejoin: A simple, worst-case optimal join algorithm. In Proc. International Conference on Database Theory (ICDT). 96--106."},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629489"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1162\/dint_a_00209"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375722"}],"event":{"name":"WWW '25: The ACM Web Conference 2025","location":"Sydney NSW Australia","acronym":"WWW '25","sponsor":["SIGWEB ACM Special Interest Group on Hypertext, Hypermedia, and Web"]},"container-title":["Proceedings of the ACM on Web Conference 2025"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3696410.3714695","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3696410.3714695","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:18:57Z","timestamp":1750281537000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3696410.3714695"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,22]]},"references-count":56,"alternative-id":["10.1145\/3696410.3714695","10.1145\/3696410"],"URL":"https:\/\/doi.org\/10.1145\/3696410.3714695","relation":{},"subject":[],"published":{"date-parts":[[2025,4,22]]},"assertion":[{"value":"2025-04-22","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}