{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T04:16:52Z","timestamp":1777954612262,"version":"3.51.4"},"publisher-location":"New York, NY, USA","reference-count":53,"publisher":"ACM","funder":[{"DOI":"10.13039\/501100006374","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF- 1901381, CCF-1910030, and CCF-1919223"],"award-info":[{"award-number":["CCF- 1901381, CCF-1910030, and CCF-1919223"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,7,16]]},"DOI":"10.1145\/3694906.3743339","type":"proceedings-article","created":{"date-parts":[[2025,7,16]],"date-time":"2025-07-16T16:19:56Z","timestamp":1752682796000},"page":"131-143","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["CLEANN: Lock-Free Augmented Trees for Low-Dimensional \u03ba-Nearest Neighbor Search"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-1038-8846","authenticated-orcid":false,"given":"Magdalen Dobson","family":"Manohar","sequence":"first","affiliation":[{"name":"Microsoft Azure, Redmond, WA, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5176-0961","authenticated-orcid":false,"given":"Yuanhao","family":"Wei","sequence":"additional","affiliation":[{"name":"University of British Columbia, Vancouver, BC, Canada"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0224-9187","authenticated-orcid":false,"given":"Guy E.","family":"Blelloch","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,7,16]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"2023. https:\/\/graphics.stanford.edu\/data\/3Dscanrep\/"},{"key":"e_1_3_2_1_2_1","unstructured":"S.J. Aarseth M. Henon and R. Wielen. 1974. Numerical methods for the study of star cluster dynamics. Astronomy and Astrophysics 37 2 (1974)."},{"key":"e_1_3_2_1_3_1","volume-title":"Linearizable Iterators for Concurrent Data Structures. CoRR abs\/1705.08885","author":"Agarwal Archita","year":"2017","unstructured":"Archita Agarwal, Zhiyu Liu, Eli Rosenthal, and Vikram Saraph. 2017. Linearizable Iterators for Concurrent Data Structures. CoRR abs\/1705.08885 (2017). arXiv:1705.08885 http:\/\/arxiv.org\/abs\/1705.08885"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Pankaj K. Agarwal Kyle Fox Kamesh Munagala and Abhinandan Nath. 2016. Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures. In Principles of Database Systems (PODS). ACM.","DOI":"10.1145\/2902251.2902303"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897826.2927362"},{"key":"e_1_3_2_1_6_1","volume-title":"Harnessing Epoch-Based Reclamation for Efficient Range Queries. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP). 14--27","author":"Arbel-Raviv Maya","year":"2018","unstructured":"Maya Arbel-Raviv and Trevor Brown. 2018. Harnessing Epoch-Based Reclamation for Efficient Range Queries. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP). 14--27."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/314464.314652"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484239.2484254"},{"key":"e_1_3_2_1_9_1","article-title":"KiWi: A Key-Value Map for Scalable Real-Time Analytics","volume":"7","author":"Basin Dmitry","year":"2020","unstructured":"Dmitry Basin, Edward Bortnikov, Anastasia Braginsky, Guy Golan-Gueta, Eshcar Hillel, Idit Keidar, and Moshe Sulamy. 2020. KiWi: A Key-Value Map for Scalable Real-Time Analytics. ACM Transactions on Parallel Computing(TOPC) 7, 3, Article 16 (June 2020), 28 pages.","journal-title":"ACM Transactions on Parallel Computing(TOPC)"},{"key":"e_1_3_2_1_10_1","unstructured":"Naama Ben-David Guy Blelloch and Yuanhao Wei. 2022. The flock library. https:\/\/github.com\/cmuparlay\/flock."},{"key":"e_1_3_2_1_11_1","volume-title":"Lock-Free Locks Revisited. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP).","author":"Ben-David Naama","year":"2022","unstructured":"Naama Ben-David, Guy Blelloch, and Yuanhao Wei. 2022. Lock-Free Locks Revisited. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP)."},{"key":"e_1_3_2_1_12_1","volume-title":"Multidimensional binary search trees used for associative searching. Commun. ACM 18, 9","author":"Bentley Jon Louis","year":"1975","unstructured":"Jon Louis Bentley. 1975. Multidimensional binary search trees used for associative searching. Commun. ACM 18, 9 (1975)."},{"key":"e_1_3_2_1_13_1","volume-title":"ParlayLib - A Toolkit for Parallel Algorithms on Shared-Memory Multicore Machines. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). https:\/\/cmuparlay.github.io\/parlaylib\/","author":"Blelloch Guy E.","year":"2020","unstructured":"Guy E. Blelloch, Daniel Anderson, and Laxman Dhulipala. 2020. ParlayLib - A Toolkit for Parallel Algorithms on Shared-Memory Multicore Machines. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). https:\/\/cmuparlay.github.io\/parlaylib\/"},{"key":"e_1_3_2_1_14_1","volume-title":"Parallel Nearest Neighbors in Low Dimensions with Batch Updates. In Symposium on Algorithm Engineering and Experiments (ALENEX). SIAM, 195--208","author":"Blelloch Guy E","year":"2022","unstructured":"Guy E Blelloch and Magdalen Dobson. 2022. Parallel Nearest Neighbors in Low Dimensions with Batch Updates. In Symposium on Algorithm Engineering and Experiments (ALENEX). SIAM, 195--208."},{"key":"e_1_3_2_1_15_1","volume-title":"VERLIB: Concurrent Versioned Pointers. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP).","author":"Guy","unstructured":"Guy E. Blelloch and Yuanhao Wei. 2024. VERLIB: Concurrent Versioned Pointers. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP)."},{"key":"e_1_3_2_1_16_1","unstructured":"Timothy Chan. 2006. A minimalist's implementation of an approximate nearest neighbor algorithm in fixed dimensions. (2006)."},{"key":"e_1_3_2_1_17_1","unstructured":"Bapi Chatterjee. 2016. ConcurrentKDTree. https:\/\/github.com\/bapi\/ConcurrentKDTree_o."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3007748.3007771"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3154273.3154307"},{"key":"e_1_3_2_1_20_1","volume-title":"Finite Elements on Point Based Surfaces. In Symposium on Point Based Graphics (PBG). Eurographics Association.","author":"Clarenz Ulrich","year":"2004","unstructured":"Ulrich Clarenz, Martin Rumpf, and Alexandru Telea. 2004. Finite Elements on Point Based Surfaces. In Symposium on Point Based Graphics (PBG). Eurographics Association."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2010.9"},{"key":"e_1_3_2_1_22_1","volume-title":"ACM Symposium on Principles and Practice of Parallel Programming (PPOPP).","author":"Dice Dave","year":"2013","unstructured":"Dave Dice, Yossi Lev, and Mark Moir. 2013. Scalable statistics counters. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP)."},{"key":"e_1_3_2_1_23_1","unstructured":"Javier Duarte. 2022. UCSD PHYS 141\/241: Computational Physics I. https:\/\/jduarte.physics.ucsd.edu\/phys141\/README.html."},{"key":"e_1_3_2_1_24_1","volume-title":"Comparison on nearest-neigbour-search strategies and implementations for efficient shape registration. Journal of Software Engineering for Robotics (JOSER) 3 (01","author":"Elseberg Jan","year":"2012","unstructured":"Jan Elseberg, S. Magnenat, Roland Siegwart, and Andreas Nuchter. 2012. Comparison on nearest-neigbour-search strategies and implementations for efficient shape registration. Journal of Software Engineering for Robotics (JOSER) 3 (01 2012)."},{"key":"e_1_3_2_1_25_1","volume-title":"Approximate counting: A detailed analysis. BIT 25, 1","author":"Flajolet Philippe","year":"1985","unstructured":"Philippe Flajolet. 1985. Approximate counting: A detailed analysis. BIT 25, 1 (1985)."},{"key":"e_1_3_2_1_26_1","unstructured":"Keir Fraser. 2004. Practical lock-freedom. Technical Report. University of Cambridge Computer Laboratory."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2851141.2851146"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/11795490_3"},{"key":"e_1_3_2_1_29_1","unstructured":"Maurice Herlihy and Nir Shavit. 2012. The Art of Multiprocessor Programming. Morgan Kaufmann."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/78969.78972"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCAS.2015.7169256"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2305.11335"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-44051-0_5"},{"key":"e_1_3_2_1_34_1","volume-title":"Adding Approximate Counters. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP).","author":"Steele Guy L.","unstructured":"Guy L. Steele Jr. and Jean-Baptiste Tristan. 2016. Adding Approximate Counters. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP)."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/868005"},{"key":"e_1_3_2_1_36_1","volume-title":"Jiffy: A Lock-Free Skip List with Batch Updates and Snapshots. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP).","author":"Kobus Tadeusz","unstructured":"Tadeusz Kobus, Maciej Kokoci\u0144ski, and Pawe\u0142 T. Wojciechowski. 2022. Jiffy: A Lock-Free Skip List with Batch Updates and Snapshots. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP)."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/320613.320619"},{"key":"e_1_3_2_1_38_1","volume-title":"ACM Internaltional Database Engineering and Applications Symposium (IDEAS).","author":"Scott","unstructured":"Scott A. Mitchell and David M. Day. 2011. Flexible approximate counting. In ACM Internaltional Database Engineering and Applications Symposium (IDEAS)."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195904001470"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/359619.359627"},{"key":"e_1_3_2_1_41_1","volume-title":"Fast Concurrent Lock-Free Binary Search Trees. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP).","author":"Natarajan Aravind","year":"2014","unstructured":"Aravind Natarajan and Neeraj Mittal. 2014. Fast Concurrent Lock-Free Binary Search Trees. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP)."},{"key":"e_1_3_2_1_42_1","volume-title":"Bundling Linked Data Structures for Linearizable Range Queries. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP). 368--384","author":"Nelson-Slivon Jacob","year":"2022","unstructured":"Jacob Nelson-Slivon, Ahmed Hassan, and Roberto Palmieri. 2022. Bundling Linked Data Structures for Linearizable Range Queries. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP). 368--384."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/580840"},{"key":"e_1_3_2_1_44_1","volume-title":"Stream-Processing Points. In 16th IEEE Visualization Conference. IEEE Computer Society.","author":"Pajarola Renato","year":"2005","unstructured":"Renato Pajarola. 2005. Stream-Processing Points. In 16th IEEE Visualization Conference. IEEE Computer Society."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/348.318588"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/882262.882319"},{"key":"e_1_3_2_1_47_1","unstructured":"D. Reed. 1978. Naming and synchronization in a decentralized computer system. Technical Report LCS\/TR-205. EECS Dept. MIT."},{"key":"e_1_3_2_1_48_1","volume-title":"Jet clustering in particle physics, via a dynamic nearest neighbour graph implemented with CGAL. (04","author":"Salam Gavin","year":"2006","unstructured":"Gavin Salam and Matteo Cacciari. 2006. Jet clustering in particle physics, via a dynamic nearest neighbour graph implemented with CGAL. (04 2006)."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457296"},{"key":"e_1_3_2_1_50_1","volume-title":"Lock-Free Locks Revisited. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP).","author":"Wei Yuanhao","unstructured":"Yuanhao Wei, Naama Ben-David, and Guy E. Blelloch. 2022. Lock-Free Locks Revisited. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP)."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3437801.3441602"},{"key":"e_1_3_2_1_52_1","volume-title":"Parallel Batch-Dynamic k-d Trees. arXiv preprint arXiv:2112.06188","author":"Yesantharao Rahul","year":"2021","unstructured":"Rahul Yesantharao, Yiqiu Wang, Laxman Dhulipala, and Julian Shun. 2021. Parallel Batch-Dynamic k-d Trees. arXiv preprint arXiv:2112.06188 (2021)."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1409060.1409079"}],"event":{"name":"SPAA '25: 37th ACM Symposium on Parallelism in Algorithms and Architectures","location":"Portland OR USA","acronym":"SPAA '25","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGARCH ACM Special Interest Group on Computer Architecture","EATCS European Association for Theoretical Computer Science"]},"container-title":["Proceedings of the 37th ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3694906.3743339","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T19:18:35Z","timestamp":1777922315000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3694906.3743339"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,16]]},"references-count":53,"alternative-id":["10.1145\/3694906.3743339","10.1145\/3694906"],"URL":"https:\/\/doi.org\/10.1145\/3694906.3743339","relation":{},"subject":[],"published":{"date-parts":[[2025,7,16]]},"assertion":[{"value":"2025-07-16","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}