{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T14:24:17Z","timestamp":1785594257514,"version":"3.56.0"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2024,11,4]],"date-time":"2024-11-04T00:00:00Z","timestamp":1730678400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"RGC","award":["14207820, 14203421, and 14222822"],"award-info":[{"award-number":["14207820, 14203421, and 14222822"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,11,4]]},"abstract":"<jats:p>\n            In a\n            <jats:italic toggle=\"yes\">spatial join<\/jats:italic>\n            , we are given a constant number k \u2265 2 of sets - denoted as R1, R2, ..., Rk - containing axis-parallel rectangles in a 2D space. The objective is to report all k-tuples (r1, r2, ..., rk ) \u2208 R1 \u00d7 R2 \u00d7 ... \u00d7 Rk where the rectangles r1, r2, ..., rk have a non-empty intersection, i.e., r1 \u2229 r2 \u2229 ... \u2229 rk \u2260 \u2205. The problem holds significant importance in spatial databases and has been extensively studied in the database community. In this paper, we show how to settle the problem in O(n logn + OUT) time - regardless of the constant k - where n = \u00cdk i=1 |Ri | and OUT is the result size (i.e., the total number of k-tuples reported). The runtime is asymptotically optimal in the class of comparison-based algorithms, to which our solution belongs. Previously, the state of the art was an algorithm with running time O(n log\n            <jats:sup>2k-1<\/jats:sup>\n            n + OUT).\n          <\/jats:p>","DOI":"10.1145\/3695828","type":"journal-article","created":{"date-parts":[[2024,11,7]],"date-time":"2024-11-07T17:26:35Z","timestamp":1731000395000},"page":"1-25","source":"Crossref","is-referenced-by-count":2,"title":["Optimal (Multiway) Spatial Joins"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-1630-9196","authenticated-orcid":false,"given":"Ru","family":"Wang","sequence":"first","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3883-5452","authenticated-orcid":false,"given":"Yufei","family":"Tao","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,11,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/10078791X"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523189"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46439-5_29"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/170035.170075"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1370949"},{"key":"e_1_2_1_6_1","volume-title":"On the complexity of computations under varying sets of primitives. Journal of Computer and System Sciences (JCSS), 18(1):86--91","author":"Dobkin David P.","year":"1979","unstructured":"David P. Dobkin and Richard J. Lipton. On the complexity of computations under varying sets of primitives. Journal of Computer and System Sciences (JCSS), 18(1):86--91, 1979."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2452376.2452390"},{"key":"e_1_2_1_8_1","volume-title":"Jacox and Hanan Samet. Spatial join techniques. ACM Transactions on Database Systems (TODS), 32(1):7","author":"Edwin","year":"2007","unstructured":"Edwin H. Jacox and Hanan Samet. Spatial join techniques. ACM Transactions on Database Systems (TODS), 32(1):7, 2007."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3517804.3524156"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253340"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/191839.191881"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233337"},{"key":"e_1_2_1_13_1","first-page":"118","volume-title":"Proceedings of ACM Symposium on Advances in Geographic Information Systems (GIS)","author":"Mamoulis Nikos","year":"1998","unstructured":"Nikos Mamoulis and Dimitris Papadias. Constraint-based algorithms for computing clique intersection joins. In Robert Laurini, Kia Makki, and Niki Pissinou, editors, Proceedings of ACM Symposium on Advances in Geographic Information Systems (GIS), pages 118--123, 1998."},{"key":"e_1_2_1_14_1","volume-title":"Multiway spatial joins. ACM Transactions on Database Systems (TODS), 26(4):424--475","author":"Mamoulis Nikos","year":"2001","unstructured":"Nikos Mamoulis and Dimitris Papadias. Multiway spatial joins. ACM Transactions on Database Systems (TODS), 26(4):424--475, 2001."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2003.1161591"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214021"},{"key":"e_1_2_1_17_1","first-page":"85","article-title":"Finding pairwise intersections of rectangles in a query rectangle","author":"Oh Eunjin","year":"2019","unstructured":"Eunjin Oh and Hee-Kap Ahn. Finding pairwise intersections of rectangles in a query rectangle. Comput. Geom., 85, 2019.","journal-title":"Comput. Geom."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303981"},{"key":"e_1_2_1_19_1","first-page":"259","volume-title":"Proceedings of ACM Management of Data (SIGMOD)","author":"Jignesh","year":"1996","unstructured":"Jignesh M. Patel and David J. DeWitt. Partition based spatial-merge join. In Proceedings of ACM Management of Data (SIGMOD), pages 259--270, 1996."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-19094-0_14"},{"key":"e_1_2_1_21_1","volume-title":"Intersection joins under updates. Journal of Computer and System Sciences (JCSS), 124:41--64","author":"Tao Yufei","year":"2022","unstructured":"Yufei Tao and Ke Yi. Intersection joins under updates. Journal of Computer and System Sciences (JCSS), 124:41--64, 2022."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3695828","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3695828","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,23]],"date-time":"2025-08-23T02:35:55Z","timestamp":1755916555000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3695828"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,4]]},"references-count":21,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,11,4]]}},"alternative-id":["10.1145\/3695828"],"URL":"https:\/\/doi.org\/10.1145\/3695828","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,4]]}}}