{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T08:54:14Z","timestamp":1775638454052,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":46,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,9]],"date-time":"2021-06-09T00:00:00Z","timestamp":1623196800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ANID Chile - Millenium Science Initiative Program","award":["CN17_002"],"award-info":[{"award-number":["CN17_002"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,9]]},"DOI":"10.1145\/3448016.3457256","type":"proceedings-article","created":{"date-parts":[[2021,6,18]],"date-time":"2021-06-18T17:22:39Z","timestamp":1624036959000},"page":"102-114","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":28,"title":["Worst-Case Optimal Graph Joins in Almost No Space"],"prefix":"10.1145","author":[{"given":"Diego","family":"Arroyuelo","sequence":"first","affiliation":[{"name":"Universidad T\u00e9cnica Federico Santa Mar\u00eda & Millennium Institute for Foundational Research on Data, Santiago, Chile"}]},{"given":"Aidan","family":"Hogan","sequence":"additional","affiliation":[{"name":"Universidad de Chile & Millennium Institute for Foundational Research on Data, Santiago, Chile"}]},{"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[{"name":"Universidad de Chile & Millennium Institute for Foundational Research on Data, Santiago, Chile"}]},{"given":"Juan L.","family":"Reutter","sequence":"additional","affiliation":[{"name":"Pontificia Universidad Cat\u00f3lica de Chile & Millennium Institute for Foundational Research on Data, Santiago, Chile"}]},{"given":"Javiel","family":"Rojas-Ledesma","sequence":"additional","affiliation":[{"name":"Universidad de Chile & Millennium Institute for Foundational Research on Data, Santiago, Chile"}]},{"given":"Adri\u00e1n","family":"Soto","sequence":"additional","affiliation":[{"name":"Universidad Adolfo Ib\u00e1\u00f1ez & Millennium Institute for Foundational Research on Data, Santiago, Chile"}]}],"member":"320","published-online":{"date-parts":[[2021,6,18]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3129246"},{"key":"e_1_3_2_2_2_1","first-page":"1","article-title":"Boolean tensor decomposition for conjunctive queries with negation","volume":"21","author":"Abo Khamis M.","year":"2019","unstructured":"M. Abo Khamis , H.Q. Ngo , D. Olteanu , and D. Suciu . 2019 . Boolean tensor decomposition for conjunctive queries with negation . In Proc. International Conference on Database Theory (ICDT). 21 : 1 -- 21 :19. M. Abo Khamis, H.Q. Ngo, D. Olteanu, and D. Suciu. 2019. Boolean tensor decomposition for conjunctive queries with negation. In Proc. International Conference on Database Theory (ICDT). 21:1--21:19.","journal-title":"Proc. International Conference on Database Theory (ICDT)."},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-014-0770-y"},{"key":"e_1_3_2_2_4_1","first-page":"1","article-title":"Box Covers and Domain Orderings for Beyond Worst-Case Join Processing","volume":"3","author":"Alway K.","year":"2021","unstructured":"K. Alway , E. Blais , and S. Salihoglu . 2021 . Box Covers and Domain Orderings for Beyond Worst-Case Join Processing . In Proc. International Conference on Database Theory (ICDT) . 3 : 1 -- 3 :23. K. Alway, E. Blais, and S. Salihoglu. 2021. Box Covers and Domain Orderings for Beyond Worst-Case Join Processing. In Proc. International Conference on Database Theory (ICDT) . 3:1--3:23.","journal-title":"Proc. International Conference on Database Theory (ICDT) ."},{"key":"e_1_3_2_2_5_1","unstructured":"D. Arroyuelo A. Hogan G. Navarro J.L. Reutter J. Rojas-Ledesma and A. Soto. 2020. Online appendix and material. https:\/\/github.com\/darroyue\/Ring.  D. Arroyuelo A. Hogan G. Navarro J.L. Reutter J. Rojas-Ledesma and A. Soto. 2020. Online appendix and material. https:\/\/github.com\/darroyue\/Ring."},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/110859440"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.02.002"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3381417"},{"key":"e_1_3_2_2_9_1","volume-title":"Proc. World Wide Web Conference (WWW) . 127--138","author":"Bonifati A.","unstructured":"A. Bonifati , W. Martens , and T. Timm . 2019. Navigating the Maze of Wikidata Query Logs . In Proc. World Wide Web Conference (WWW) . 127--138 . A. Bonifati, W. Martens, and T. Timm. 2019. Navigating the Maze of Wikidata Query Logs. In Proc. World Wide Web Conference (WWW) . 127--138."},{"key":"e_1_3_2_2_10_1","volume-title":"Proc. International Symposium on String Processing and Information Retrieval (SPIRE). 103--115","author":"Brisaboa N.","unstructured":"N. Brisaboa , A. Cerdeira , A. Fari na, and G. Navarro . 2015. A compact RDF store using suffix arrays . In Proc. International Symposium on String Processing and Information Retrieval (SPIRE). 103--115 . N. Brisaboa, A. Cerdeira, A. Fari na, and G. Navarro. 2015. A compact RDF store using suffix arrays. In Proc. International Symposium on String Processing and Information Retrieval (SPIRE). 103--115."},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2017.05.003"},{"key":"e_1_3_2_2_12_1","volume-title":"Technical Report 124. Digital Equipment Corporation.","author":"Burrows M.","year":"1994","unstructured":"M. Burrows and D. Wheeler . 1994 . A block sorting lossless data compression algorithm . Technical Report 124. Digital Equipment Corporation. M. Burrows and D. Wheeler. 1994. A block sorting lossless data compression algorithm . Technical Report 124. Digital Equipment Corporation."},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2014.06.002"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"crossref","unstructured":"O. Erling and I. Mikhailov. 2009. RDF support in the Virtuoso DBMS . In Networked Knowledge -- Networked Media .  O. Erling and I. Mikhailov. 2009. RDF support in the Virtuoso DBMS . In Networked Knowledge -- Networked Media .","DOI":"10.1007\/978-3-642-02184-8_2"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2013.01.002"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1082036.1082039"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1240233.1240243"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407797"},{"key":"e_1_3_2_2_20_1","volume-title":"Theoretical Computer Science","volume":"483","author":"Gagie T.","year":"2013","unstructured":"T. Gagie , J. K\"arkk\"ainen, G. Navarro , and S.J. Puglisi . 2013. Colored range queries and document retrieval . Theoretical Computer Science , Vol. 483 ( 2013 ), 36--50. T. Gagie, J. K\"arkk\"ainen, G. Navarro, and S.J. Puglisi. 2013. Colored range queries and document retrieval. Theoretical Computer Science , Vol. 483 (2013), 36--50."},{"key":"e_1_3_2_2_21_1","volume-title":"Theoretical Computer Science","volume":"427","author":"Gagie T.","year":"2012","unstructured":"T. Gagie , G. Navarro , and S. J. Puglisi . 2012. New algorithms on wavelet trees and applications to Information Retrieval . Theoretical Computer Science , Vol. 426-- 427 ( 2012 ), 25--41. T. Gagie, G. Navarro, and S. J. Puglisi. 2012. New algorithms on wavelet trees and applications to Information Retrieval. Theoretical Computer Science , Vol. 426--427 (2012), 25--41."},{"key":"e_1_3_2_2_22_1","volume-title":"Proc. Symposium on Discrete Algorithms (SODA) . 841--850","author":"Grossi R.","unstructured":"R. Grossi , A. Gupta , and J. S. Vitter . 2003. High-order entropy-compressed text indexes . In Proc. Symposium on Discrete Algorithms (SODA) . 841--850 . R. Grossi, A. Gupta, and J. S. Vitter. 2003. High-order entropy-compressed text indexes. In Proc. Symposium on Discrete Algorithms (SODA) . 841--850."},{"key":"e_1_3_2_2_23_1","volume-title":"Proc. International Semantic Web Conference (ISWC). 258--275","author":"Hogan A.","unstructured":"A. Hogan , C. Riveros , C. Rojas , and A. Soto . 2019. A worst-case optimal join algorithm for SPARQL . In Proc. International Semantic Web Conference (ISWC). 258--275 . A. Hogan, C. Riveros, C. Rojas, and A. Soto. 2019. A worst-case optimal join algorithm for SPARQL . In Proc. International Semantic Web Conference (ISWC). 258--275."},{"key":"e_1_3_2_2_24_1","volume-title":"Proc. International Conference on Extending Database Technology (EDBT). 282--293","author":"Kalinsky O.","unstructured":"O. Kalinsky , Y. Etsion , and B. Kimelfeld . 2017. Flexible caching in trie joins . In Proc. International Conference on Extending Database Technology (EDBT). 282--293 . O. Kalinsky, Y. Etsion, and B. Kimelfeld. 2017. Flexible caching in trie joins. In Proc. International Conference on Extending Database Technology (EDBT). 282--293."},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2967101"},{"key":"e_1_3_2_2_26_1","volume-title":"Proc. Symposium on Principles of Database Systems (PODS). 429--444","author":"Khamis M. A.","unstructured":"M. A. Khamis , H. Q. Ngo , and D. Suciu . 2017. What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? . In Proc. Symposium on Principles of Database Systems (PODS). 429--444 . M. A. Khamis, H. Q. Ngo, and D. Suciu. 2017. What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?. In Proc. Symposium on Principles of Database Systems (PODS). 429--444."},{"key":"e_1_3_2_2_27_1","article-title":"Dynamic entropy-compressed sequences and full-text indexes","volume":"4","author":"Navarro V.","year":"2008","unstructured":"V. M\"akinen and G. Navarro . 2008 . Dynamic entropy-compressed sequences and full-text indexes . ACM Transactions on Algorithms , Vol. 4 , 3, Article 32 (2008). V. M\"akinen and G. Navarro. 2008. Dynamic entropy-compressed sequences and full-text indexes. ACM Transactions on Algorithms , Vol. 4, 3, Article 32 (2008).","journal-title":"ACM Transactions on Algorithms"},{"key":"e_1_3_2_2_28_1","volume-title":"Proc. International Semantic Web Conference (ISWC). 376--394","author":"Malyshev S.","unstructured":"S. Malyshev , M. Kr\u00f6 tzsch, L. Gonz\u00e1 lez, J. Gonsior , and A. Bielefeldt . 2018. Getting the most out of Wikidata: Semantic technology usage in Wikipedia's knowledge graph . In Proc. International Semantic Web Conference (ISWC). 376--394 . S. Malyshev, M. Kr\u00f6 tzsch, L. Gonz\u00e1 lez, J. Gonsior, and A. Bielefeldt. 2018. Getting the most out of Wikidata: Semantic technology usage in Wikipedia's knowledge graph. In Proc. International Semantic Web Conference (ISWC). 376--394."},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.07.014"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342643"},{"key":"e_1_3_2_2_31_1","volume-title":"Tables. In Proc. Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). 37--42","author":"Munro J. I.","year":"1996","unstructured":"J. I. Munro . 1996 . Tables. In Proc. Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). 37--42 . J. I. Munro. 1996. Tables. In Proc. Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). 37--42."},{"key":"e_1_3_2_2_32_1","volume-title":"Proc. Symposium on Principles of Database Systems (PODS). 277--289","author":"Munro J. I.","unstructured":"J. I. Munro , Y. Nekrich , and J. S. Vitter . 2015. Dynamic Data Structures for Document Collections and Graphs . In Proc. Symposium on Principles of Database Systems (PODS). 277--289 . J. I. Munro, Y. Nekrich, and J. S. Vitter. 2015. Dynamic Data Structures for Document Collections and Graphs. In Proc. Symposium on Principles of Database Systems (PODS). 277--289."},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.11.011"},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2013.07.004"},{"key":"e_1_3_2_2_35_1","first-page":"1","article-title":"Optimal joins using compact data structures","volume":"21","author":"Navarro G.","year":"2020","unstructured":"G. Navarro , J. Reutter , and J. Rojas . 2020 . Optimal joins using compact data structures . In Proc. International Conference on Database Theory (ICDT). 21 : 1 -- 21 :21. G. Navarro, J. Reutter, and J. Rojas. 2020. Optimal joins using compact data structures. In Proc. International Conference on Database Theory (ICDT). 21:1--21:21.","journal-title":"Proc. International Conference on Database Theory (ICDT)."},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0165-y"},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196990"},{"key":"e_1_3_2_2_38_1","volume-title":"Proc. Symposium on Principles of Database Systems (PODS). 37--48","author":"Ngo H. Q.","unstructured":"H. Q. Ngo , E. Porat , C. R\u00e9 , and A. Rudra . 2012. Worst-case optimal join algorithms . In Proc. Symposium on Principles of Database Systems (PODS). 37--48 . H. Q. Ngo, E. Porat, C. R\u00e9, and A. Rudra. 2012. Worst-case optimal join algorithms. In Proc. Symposium on Principles of Database Systems (PODS). 37--48."},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2590989.2590991"},{"key":"e_1_3_2_2_40_1","first-page":"1","article-title":"Join processing for graph patterns: An old dog with new tricks","volume":"2","author":"Nguyen D.","year":"2015","unstructured":"D. Nguyen , M. Aref , M. Bravenboer , G. Kollias , H. Q. Ngo , C. R\u00e9 , and A. Rudra . 2015 . Join processing for graph patterns: An old dog with new tricks . In Proc. International Workshop on Graph Data Management Experiences and Systems (GRADES) . 2 : 1 -- 2 :8. D. Nguyen, M. Aref, M. Bravenboer, G. Kollias, H. Q. Ngo, C. R\u00e9, and A. Rudra. 2015. Join processing for graph patterns: An old dog with new tricks. In Proc. International Workshop on Graph Data Management Experiences and Systems (GRADES) . 2:1--2:8.","journal-title":"Proc. International Workshop on Graph Data Management Experiences and Systems (GRADES) ."},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00087-7"},{"key":"e_1_3_2_2_42_1","unstructured":"B. B. Thompson M. Personick and M. Cutcher. 2014. The Bigdata\u00ae RDF Graph Database . In Linked Data Management . 193--237.  B. B. Thompson M. Personick and M. Cutcher. 2014. The Bigdata\u00ae RDF Graph Database . In Linked Data Management . 193--237."},{"key":"e_1_3_2_2_43_1","volume-title":"Proc. SIGMOD International Conference on Management of Data. 2659--2665","author":"Tziavelis N.","unstructured":"N. Tziavelis , W. Gatterbauer , and M. Riedewald . 2020. Optimal Join Algorithms Meet Top-k . In Proc. SIGMOD International Conference on Management of Data. 2659--2665 . N. Tziavelis, W. Gatterbauer, and M. Riedewald. 2020. Optimal Join Algorithms Meet Top-k. In Proc. SIGMOD International Conference on Management of Data. 2659--2665."},{"key":"e_1_3_2_2_44_1","volume-title":"Proc. International Conference on Database Theory (ICDT). 96--106","author":"Veldhuizen T. L.","year":"2014","unstructured":"T. L. Veldhuizen . 2014 . Triejoin: A simple, worst-case optimal join algorithm . In Proc. International Conference on Database Theory (ICDT). 96--106 . T. 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_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629489"},{"key":"e_1_3_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453965"},{"key":"e_1_3_2_2_47_1","volume-title":"Proc. International Conference on Very Large Databases (VLDB). 82--94","author":"Yannakakis M.","year":"1981","unstructured":"M. Yannakakis . 1981 . Algorithms for acyclic database schemes . In Proc. International Conference on Very Large Databases (VLDB). 82--94 . M. Yannakakis. 1981. Algorithms for acyclic database schemes. In Proc. International Conference on Very Large Databases (VLDB). 82--94."}],"event":{"name":"SIGMOD\/PODS '21: International Conference on Management of Data","location":"Virtual Event China","acronym":"SIGMOD\/PODS '21","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"]},"container-title":["Proceedings of the 2021 International Conference on Management of Data"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3448016.3457256","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3448016.3457256","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:28:06Z","timestamp":1750195686000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3448016.3457256"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,9]]},"references-count":46,"alternative-id":["10.1145\/3448016.3457256","10.1145\/3448016"],"URL":"https:\/\/doi.org\/10.1145\/3448016.3457256","relation":{},"subject":[],"published":{"date-parts":[[2021,6,9]]},"assertion":[{"value":"2021-06-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}