{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,23]],"date-time":"2026-10-23T23:44:33Z","timestamp":1792799073755,"version":"4.5.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,5,23]],"date-time":"2022-05-23T00:00:00Z","timestamp":1653264000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ANID-Millennium Science Initiative Program","award":["ICN17_002"],"award-info":[{"award-number":["ICN17_002"]}],"id":[{"id":"https:\/\/ror.org\/01c080z51","id-type":"ROR","asserted-by":"crossref"}]},{"name":"Fondecyt","award":["1-200038"],"award-info":[{"award-number":["1-200038"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2022,6,30]]},"abstract":"<jats:p>\n                    Worst-case optimal join algorithms have gained a lot of attention in the database literature. We now count several algorithms that are optimal in the worst case, and many of them have been implemented and validated in practice. However, the implementation of these algorithms often requires an enhanced indexing structure: to achieve optimality one either needs to build completely new indexes or must populate the database with several instantiations of indexes such as B\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( + \\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    -trees. Either way, this means spending an extra amount of storage space that is typically one or two orders of magnitude more than what is required to store the raw data.\n                  <\/jats:p>\n                  <jats:p>We show that worst-case optimal algorithms can be obtained directly from a representation that regards the relations as point sets in variable-dimensional grids, without the need of any significant extra storage. Our representation is a compressed quadtreefor the static indexes and a quadtreebuilt on the fly that shares subtrees (which we dub a qdag) for intermediate results. We develop a compositional algorithm to process full join queries under this representation, which simulates navigation of the quadtreeof the output, and show that the running time of this algorithm is worst-case optimal in data complexity.<\/jats:p>\n                  <jats:p>We implement our index and compare it experimentally with state-of-the-art alternatives. Our experiments show that our index uses even less space than what is needed to store the data in raw form (and replaces it) and one or two orders of magnitude less space than the other indexes. At the same time, our query algorithm is competitive in time, even sharply outperforming other indexes in various cases.<\/jats:p>\n                  <jats:p>Finally, we extend our framework to evaluate more expressive queries from relational algebra, including not only joins and intersections but also unions and negations. To obtain optimality on those more complex formulas, we introduce a lazy version of qdagswe dub lqdags, which allow us navigate over the quadtreerepresenting the output of a formula while only evaluating what is needed from its components. We show that the running time of our query algorithms on this extended set of operations is worst-case optimal under some constraints. Moving to full relational algebra, we also show that lqdagscan handle selections and projections. While worst-case optimality is no longer guaranteed, we introduce a partial materialization scheme that extends results from Deep and Koutris regarding compressed representation of query results.<\/jats:p>","DOI":"10.1145\/3514231","type":"journal-article","created":{"date-parts":[[2022,2,23]],"date-time":"2022-02-23T16:04:25Z","timestamp":1645632265000},"page":"1-53","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Optimal Joins Using Compressed Quadtrees"],"prefix":"10.1145","volume":"47","author":[{"given":"Diego","family":"Arroyuelo","sequence":"first","affiliation":[{"name":"DIINF, UTFSM &amp; IMFD, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[{"name":"DCC, U. of Chile &amp; IMFD, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Juan L.","family":"Reutter","sequence":"additional","affiliation":[{"name":"DCC, PUC &amp; IMFD, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3208-1880","authenticated-orcid":false,"given":"Javiel","family":"Rojas-Ledesma","sequence":"additional","affiliation":[{"name":"DCC, U. of Chile &amp; IMFD, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,5,23]]},"reference":[{"key":"e_1_3_4_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3129246"},{"key":"e_1_3_4_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01940874"},{"key":"e_1_3_4_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-014-0770-y"},{"key":"e_1_3_4_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457256"},{"key":"e_1_3_4_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipm.2018.05.007"},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/110859440"},{"key":"e_1_3_4_8_2","doi-asserted-by":"publisher","DOI":"10.5555\/3118737.3118845"},{"key":"e_1_3_4_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2017.05.003"},{"key":"e_1_3_4_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2013.08.003"},{"key":"e_1_3_4_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196979"},{"key":"e_1_3_4_12_2","volume-title":"Networked Knowledge \u2013 Networked Media","author":"Erling O.","year":"2009","unstructured":"O. Erling and I. Mikhailov. 2009. RDF support in the Virtuoso DBMS. In Networked Knowledge \u2013 Networked Media. Springer."},{"key":"e_1_3_4_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288933"},{"key":"e_1_3_4_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2015.57"},{"key":"e_1_3_4_15_2","doi-asserted-by":"publisher","DOI":"10.1002\/spe.2198"},{"key":"e_1_3_4_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/2220357.2220363"},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-30793-6_15"},{"key":"e_1_3_4_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/B978-012088469-8.50005-X"},{"issue":"4","key":"e_1_3_4_19_2","first-page":"22","article-title":"Joins via geometric resolutions: Worst case and beyond","volume":"41","author":"Khamis M. A.","year":"2016","unstructured":"M. A. Khamis, H. Q. Ngo, C. R\u00e9, and A. Rudra. 2016. Joins via geometric resolutions: Worst case and beyond. ACM Trans. Datab. Syst. 41, 4 (2016), 22.","journal-title":"ACM Trans. Datab. Syst."},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902280"},{"key":"e_1_3_4_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056105"},{"key":"e_1_3_4_22_2","volume-title":"The Art of Computer Programming, Volume 4, Fascicle 1: Bitwise Tricks & Techniques; Binary Decision Diagrams (12th ed.)","author":"Knuth D. E.","year":"2009","unstructured":"D. E. Knuth. 2009. The Art of Computer Programming, Volume 4, Fascicle 1: Bitwise Tricks & Techniques; Binary Decision Diagrams (12th ed.). Addison-Wesley Professional."},{"key":"e_1_3_4_23_2","article-title":"SNAP Datasets: Stanford Large Network Dataset Collection","author":"Leskovec J.","year":"2014","unstructured":"J. Leskovec and A. Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved fromhttp:\/\/snap.stanford.edu\/data.","journal-title":"Retrieved fromhttp:\/\/snap.stanford.edu\/data"},{"key":"e_1_3_4_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-00668-6_23"},{"key":"e_1_3_4_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2015.08.008"},{"key":"e_1_3_4_26_2","volume-title":"A Computer-oriented Geodetic Data Base; and a New Technique in File Sequencing","author":"Morton G. M.","year":"1966","unstructured":"G. M. Morton. 1966. A Computer-oriented Geodetic Data Base; and a New Technique in File Sequencing. Technical Report. IBM Ltd."},{"key":"e_1_3_4_27_2","doi-asserted-by":"publisher","DOI":"10.5555\/646834.708184"},{"key":"e_1_3_4_28_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781316588284"},{"key":"e_1_3_4_29_2","first-page":"21:1\u201321:21","volume-title":"Proceedings of the 23rd International Conference on Database Theory (ICDT)","author":"Navarro G.","year":"2020","unstructured":"G. Navarro, J. Reutter, and J. Rojas-Ledesma. 2020. Optimal joins using compact data structures. In Proceedings of the 23rd International Conference on Database Theory (ICDT). 21:1\u201321:21."},{"issue":"3","key":"e_1_3_4_30_2","article-title":"Fully-functional static and dynamic succinct trees","volume":"10","author":"Navarro G.","year":"2014","unstructured":"G. Navarro and K. Sadakane. 2014. Fully-functional static and dynamic succinct trees. ACM Trans. Algor. 10, 3 (2014).","journal-title":"ACM Trans. Algor."},{"key":"e_1_3_4_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0165-y"},{"key":"e_1_3_4_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196990"},{"key":"e_1_3_4_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594547"},{"key":"e_1_3_4_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213565"},{"key":"e_1_3_4_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/2590989.2590991"},{"key":"e_1_3_4_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/2764947.2764948"},{"key":"e_1_3_4_37_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972870.6"},{"key":"e_1_3_4_38_2","volume-title":"Foundations of Multidimensional and Metric Data Structures","author":"Samet H.","year":"2006","unstructured":"H. Samet. 2006. Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann."},{"key":"e_1_3_4_39_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84628-959-0"},{"key":"e_1_3_4_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056449"},{"key":"e_1_3_4_41_2","doi-asserted-by":"publisher","DOI":"10.1201\/b16859-12"},{"key":"e_1_3_4_42_2","first-page":"96","volume-title":"Proceedings of the 17th International Conference on Database Theory (ICDT)","author":"Veldhuizen T. L.","year":"2014","unstructured":"T. L. Veldhuizen. 2014. Triejoin: A simple, worst-case optimal join algorithm. In Proceedings of the 17th International Conference on Database Theory (ICDT). 96\u2013106."},{"key":"e_1_3_4_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/2629489"},{"key":"e_1_3_4_44_2","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(90)90079-5"},{"key":"e_1_3_4_45_2","first-page":"82","volume-title":"Proceedings of the 7th International Conference on Very Large Databases (VLDB)","author":"Yannakakis M.","year":"1981","unstructured":"M. Yannakakis. 1981. Algorithms for acyclic database schemes. In Proceedings of the 7th International Conference on Very Large Databases (VLDB). 82\u201394."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3514231","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3514231","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T14:10:14Z","timestamp":1750169414000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3514231"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,23]]},"references-count":44,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,6,30]]}},"alternative-id":["10.1145\/3514231"],"URL":"https:\/\/doi.org\/10.1145\/3514231","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,5,23]]},"assertion":[{"value":"2020-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-05-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}