{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,30]],"date-time":"2026-01-30T05:48:31Z","timestamp":1769752111293,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":69,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,1,28]],"date-time":"2026-01-28T00:00:00Z","timestamp":1769558400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-2238358"],"award-info":[{"award-number":["CCF-2238358"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-2339310"],"award-info":[{"award-number":["CCF-2339310"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["IIS-2227669"],"award-info":[{"award-number":["IIS-2227669"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["TI-2346223"],"award-info":[{"award-number":["TI-2346223"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,1,28]]},"DOI":"10.1145\/3774934.3786412","type":"proceedings-article","created":{"date-parts":[[2026,1,28]],"date-time":"2026-01-28T15:25:57Z","timestamp":1769613957000},"page":"150-163","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Parallel Dynamic Spatial Indexes"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7290-690X","authenticated-orcid":false,"given":"Ziyang","family":"Men","sequence":"first","affiliation":[{"name":"University of California at Riverside, Riverside, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-9314-1096","authenticated-orcid":false,"given":"Bo","family":"Huang","sequence":"additional","affiliation":[{"name":"University of California at Riverside, Riverside, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4392-4022","authenticated-orcid":false,"given":"Yan","family":"Gu","sequence":"additional","affiliation":[{"name":"University of California at Riverside, Riverside, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3212-0934","authenticated-orcid":false,"given":"Yihan","family":"Sun","sequence":"additional","affiliation":[{"name":"University of California at Riverside, Riverside, USA"}]}],"member":"320","published-online":{"date-parts":[[2026,1,28]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Daniar Achakeev Marc Seidemann Markus Schmidt and Bernhard Seeger. 2012. Sort-based parallel loading of R-trees. In BigSpatial@ACM Special Interest Group on Spatial Information (SIGSPATIAL). 62\u201370.","DOI":"10.1145\/2447481.2447489"},{"key":"e_1_3_2_1_2_1","volume-title":"Implementing Sets Effciently in a Functional Language","author":"Adams Stephen","unstructured":"Stephen Adams. 1992. Implementing Sets Effciently in a Functional Language. University of Southampton."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796800000885"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1201\/b22086"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3503221.3508422"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-63238-7_38"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1328911.1328920"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0107-6"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002240011004"},{"key":"e_1_3_2_1_10_1","volume-title":"European Symposium on Algorithms (ESA).","author":"Axtmann Michael","year":"2017","unstructured":"Michael Axtmann, Sascha Witt, Daniel Ferizovic, and Peter Sanders. 2017. In-place parallel super scalar samplesort (ipsssso). In European Symposium on Algorithms (ESA)."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.98741"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90117-0"},{"key":"e_1_3_2_1_14_1","volume-title":"Proceedings of the VLDB Endowment (PVLDB). Morgan Kaufmann, 28\u201339","author":"Berchtold Stefan","year":"1996","unstructured":"Stefan Berchtold, Daniel A. Keim, and Hans-Peter Kriegel. 1996. The X-tree : An Index Structure for High-Dimensional Data. In Proceedings of the VLDB Endowment (PVLDB). Morgan Kaufmann, 28\u201339."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2014.12.001"},{"key":"e_1_3_2_1_16_1","volume-title":"ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 507\u2013509","author":"Blelloch Guy E.","year":"2020","unstructured":"Guy E. Blelloch, Daniel Anderson, and Laxman Dhulipala. 2020. ParlayLib \u2014 a toolkit for parallel algorithms on shared-memory multicore machines. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 507\u2013509."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Guy E Blelloch and Magdalen Dobson. 2022. Parallel Nearest Neighbors in Low Dimensions with Batch Updates. In Algorithm Engineering and Experiments (ALENEX). 195\u2013208.","DOI":"10.1137\/1.9781611977042.16"},{"key":"e_1_3_2_1_18_1","volume-title":"Just Join for Parallel Ordered Sets. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).","author":"Blelloch Guy E.","year":"2016","unstructured":"Guy E. Blelloch, Daniel Ferizovic, and Yihan Sun. 2016. Just Join for Parallel Ordered Sets. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3350755.3400227"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1810479.1810519"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793259471"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0255(96)00219-8"},{"key":"e_1_3_2_1_23_1","volume-title":"PaC-trees: Supporting Parallel and Compressed Purely-Functional Collections. In ACM Conference on Programming Language Design and Implementation (PLDI).","author":"Dhulipala Laxman","year":"2022","unstructured":"Laxman Dhulipala, Guy E. Blelloch, Yan Gu, and Yihan Sun. 2022. PaC-trees: Supporting Parallel and Compressed Purely-Functional Collections. In ACM Conference on Programming Language Design and Implementation (PLDI)."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1653771.1653865"},{"key":"e_1_3_2_1_25_1","volume-title":"Quad trees a data structure for retrieval on composite keys. Acta informatica, 4","author":"Finkel Raphael A","year":"1974","unstructured":"Raphael A Finkel and Jon Louis Bentley. 1974. Quad trees a data structure for retrieval on composite keys. Acta informatica, 4 (1974), 1\u20139."},{"key":"e_1_3_2_1_26_1","volume-title":"Cache-Oblivious Algorithms. In IEEE Symposium on Foundations of Computer Science (FOCS).","author":"Frigo Matteo","year":"1999","unstructured":"Matteo Frigo, Charles E. Leiserson, Harald Prokop, and Sridhar Ramachandran. 1999. Cache-Oblivious Algorithms. In IEEE Symposium on Foundations of Computer Science (FOCS)."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3083897"},{"key":"e_1_3_2_1_28_1","volume-title":"ACM International Symposium on Advances in Geographic Information System (SIGSPATIAL GIS). 163\u2013164","author":"Yv\u00e1n J","year":"1998","unstructured":"Yv\u00e1n J Garc\u00eda R, Mario A L\u00f3pez, and Scott T Leutenegger. 1998. A greedy algorithm for bulk loading R-trees. In ACM International Symposium on Advances in Geographic Information System (SIGSPATIAL GIS). 163\u2013164."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12769"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Yan Gu Yong He Kayvon Fatahalian and Guy Blelloch. 2013. Efficient BVH construction via approximate agglomerative clustering. In High-Performance Graphics (HPG).","DOI":"10.1145\/2492045.2492054"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3558481.3591069"},{"key":"e_1_3_2_1_32_1","volume-title":"Analysis of Work-Stealing and Parallel Cache Complexity. In SIAM Symposium on Algorithmic Principles of Computer Systems (APOCS). 46\u201360","author":"Gu Yan","year":"2022","unstructured":"Yan Gu, Zachary Napier, and Yihan Sun. 2022. Analysis of Work-Stealing and Parallel Cache Complexity. In SIAM Symposium on Algorithmic Principles of Computer Systems (APOCS). 46\u201360."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"key":"e_1_3_2_1_34_1","volume-title":"Openstreetmap: User-generated street maps","author":"Haklay Mordechai","year":"2008","unstructured":"Mordechai Haklay and Patrick Weber. 2008. Openstreetmap: User-generated street maps. IEEE Pervasive computing, 7, 4 (2008), 12\u201318."},{"key":"e_1_3_2_1_35_1","first-page":"3","article-title":"Four-dimensional Hilbert curves for R-trees","volume":"16","author":"Haverkort Herman","year":"2008","unstructured":"Herman Haverkort and Freek V Walderveen. 2008. Four-dimensional Hilbert curves for R-trees. Journal of Experimental Algorithmics (JEA), 16 (2008), 3\u20131.","journal-title":"Journal of Experimental Algorithmics (JEA)"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0146-664X(80)90055-6"},{"key":"e_1_3_2_1_37_1","volume-title":"Parallel R-trees. ACM SIGMOD International Conference on Management of Data (SIGMOD), 21","author":"Kamel Ibrahim","year":"1992","unstructured":"Ibrahim Kamel and Christos Faloutsos. 1992. Parallel R-trees. ACM SIGMOD International Conference on Management of Data (SIGMOD), 21, 2 (1992), 195\u2013204."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/170088.170403"},{"key":"e_1_3_2_1_39_1","volume-title":"2013 IEEE 29th international conference on data engineering (ICDE). 266\u2013277","author":"Kim Jinha","year":"2013","unstructured":"Jinha Kim, Seung-Keol Kim, and Hwanjo Yu. 2013. Scalable and parallelizable processing of influence maximization for large-scale social networks? In 2013 IEEE 29th international conference on data engineering (ICDE). 266\u2013277."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2009.01377.x"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.1997.582015"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASPDAC.2012.6164973"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2023.106151"},{"key":"e_1_3_2_1_44_1","unstructured":"Ziyang Men Bo Huang Yan Gu and Yihan Sun. 2025. Parallel Dynamic Spatial Indexes. https:\/\/github.com\/ucrparlay\/SpaceTreeLib"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","unstructured":"Ziyang Men Bo Huang Yan Gu and Yihan Sun. 2025. Parallel Dynamic Spatial Indexes. https:\/\/doi.org\/10.5281\/zenodo.18011501 10.5281\/zenodo.18011501","DOI":"10.5281\/zenodo.18011501"},{"key":"e_1_3_2_1_46_1","unstructured":"Ziyang Men Bo Huang Yan Gu and Yihan Sun. 2026. Parallel Dynamic Spatial Indexes. arXiv preprint arXiv:2601.05347."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3709712"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-58435-8_181"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.1990.113481"},{"key":"e_1_3_2_1_50_1","volume-title":"HLBVH: Hierarchical LBVH construction for real-time ray tracing of dynamic geometry. In High Performance Graphics (HPG). 87\u201395.","author":"Pantaleoni Jacopo","year":"2010","unstructured":"Jacopo Pantaleoni and David Luebke. 2010. HLBVH: Hierarchical LBVH construction for real-time ray tracing of dynamic geometry. In High Performance Graphics (HPG). 87\u201395."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2003.05.003"},{"key":"e_1_3_2_1_52_1","volume-title":"GPU-based Parallel R-tree Construction and Querying. In IEEE International Parallel and Distributed Processing Symposium (IPDPS) Workshop. 618\u2013627","author":"Prasad Sushil K","year":"2015","unstructured":"Sushil K Prasad, Michael McDermott, Xi He, and Satish Puri. 2015. GPU-based Parallel R-tree Construction and Querying. In IEEE International Parallel and Distributed Processing Symposium (IPDPS) Workshop. 618\u2013627."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3187009.3177738"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3397506"},{"key":"e_1_3_2_1_55_1","unstructured":"Boris Sch\u00e4ling. 2011. The boost C++ libraries. Boris Sch\u00e4ling."},{"key":"e_1_3_2_1_56_1","volume-title":"Leutenegger","author":"Schnitzer Bernd","year":"1999","unstructured":"Bernd Schnitzer and Scott T. Leutenegger. 1999. Master-Client R-Trees: A New Parallel R-Tree Architecture. In SSDBM. IEEE Computer Society, 68\u201377."},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1086\/516585"},{"key":"e_1_3_2_1_58_1","volume-title":"Proceedings of the VLDB Endowment (PVLDB). Morgan Kaufmann, 507\u2013518","author":"Sellis Timos K.","year":"1987","unstructured":"Timos K. Sellis, Nick Roussopoulos, and Christos Faloutsos. 1987. The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. In Proceedings of the VLDB Endowment (PVLDB). Morgan Kaufmann, 507\u2013518."},{"key":"e_1_3_2_1_59_1","volume-title":"Proceedings of the VLDB Endowment (PVLDB). Morgan Kaufmann, 507\u2013518","author":"Sellis Timos K.","year":"1987","unstructured":"Timos K. Sellis, Nick Roussopoulos, and Christos Faloutsos. 1987. The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. In Proceedings of the VLDB Endowment (PVLDB). Morgan Kaufmann, 507\u2013518."},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44431-9_9"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178487.3178509"},{"key":"e_1_3_2_1_62_1","unstructured":"Herbert Tropf and Helmut Herzog. 1981. Multidimensional Range Search in Dynamically Balanced Trees.. Angewandte Info. 71\u201377."},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/3233309"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2007.11.004"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/169627.169640"},{"key":"e_1_3_2_1_66_1","unstructured":"Rahul Yesantharao Yiqiu Wang Laxman Dhulipala and Julian Shun. 2021. Parallel Batch-Dynamic k d-Trees. arXiv preprint arXiv:2112.06188."},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/2534921.2534949"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/3694906.3743318"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/3774934.3786411"}],"event":{"name":"PPoPP '26: 31st ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming","location":"Sydney NSW Australia","acronym":"PPoPP '26","sponsor":["SIGHPC ACM Special Interest Group on High Performance Computing, Special Interest Group on High Performance Computing","SIGPLAN ACM Special Interest Group on Programming Languages"]},"container-title":["Proceedings of the 31st ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3774934.3786412","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3774934.3786412","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,28]],"date-time":"2026-01-28T15:26:37Z","timestamp":1769613997000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3774934.3786412"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,28]]},"references-count":69,"alternative-id":["10.1145\/3774934.3786412","10.1145\/3774934"],"URL":"https:\/\/doi.org\/10.1145\/3774934.3786412","relation":{},"subject":[],"published":{"date-parts":[[2026,1,28]]},"assertion":[{"value":"2026-01-28","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}