{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T18:43:42Z","timestamp":1783536222339,"version":"3.55.0"},"publisher-location":"New York, NY, USA","reference-count":62,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,7,6]],"date-time":"2026-07-06T00:00:00Z","timestamp":1783296000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"name":"NSF grant","award":["IIS-2227669"],"award-info":[{"award-number":["IIS-2227669"]}]},{"name":"NSF grant","award":["TI-2346223"],"award-info":[{"award-number":["TI-2346223"]}]},{"name":"NSF CAREER Award","award":["CCF-2238358"],"award-info":[{"award-number":["CCF-2238358"]}]},{"name":"NSF CAREER Award","award":["CCF-2339310"],"award-info":[{"award-number":["CCF-2339310"]}]},{"name":"Google Research Scholar Program"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,7,6]]},"DOI":"10.1145\/3816782.3819182","type":"proceedings-article","created":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T17:28:33Z","timestamp":1783531713000},"page":"182-195","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Parallel Metric Skip Lists and Nearest Neighbor Search"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-8367-8399","authenticated-orcid":false,"given":"Xiangyun","family":"Ding","sequence":"first","affiliation":[{"name":"University of California, Riverside, Riverside, California, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-9708-9489","authenticated-orcid":false,"given":"Rohin","family":"Garg","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, Massachusetts, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4392-4022","authenticated-orcid":false,"given":"Yan","family":"Gu","sequence":"additional","affiliation":[{"name":"University of California, Riverside, Riverside, California, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3212-0934","authenticated-orcid":false,"given":"Yihan","family":"Sun","sequence":"additional","affiliation":[{"name":"University of California, Riverside, Riverside, California, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,7,8]]},"reference":[{"key":"e_1_3_2_1_1_1","article-title":"A survey on nearest neighbor search methods","volume":"95","author":"Abbasifard Mohammad Reza","year":"2014","unstructured":"Mohammad Reza Abbasifard, Bijan Ghahremani, and Hassan Naderi. 2014. A survey on nearest neighbor search methods. International Journal of Computer Applications 95, 25 (2014).","journal-title":"International Journal of Computer Applications"},{"key":"e_1_3_2_1_2_1","volume-title":"Approximate nearest-neighbor search for line segments. arXiv preprint arXiv:2103.16071","author":"Abdelkader Ahmed","year":"2021","unstructured":"Ahmed Abdelkader and David M Mount. 2021. Approximate nearest-neighbor search for line segments. arXiv preprint arXiv:2103.16071 (2021)."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/98524.98567"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1080\/00031305.1992.10475879"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002240011004"},{"key":"e_1_3_2_1_6_1","volume-title":"The uniform metric on product spaces. Lecture Notes","author":"Bell Jordan","unstructured":"Jordan Bell. [n.d.]. The uniform metric on product spaces. Lecture Notes, University of Toronto ([n. d.])."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143857"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977042.16"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3350755.3400227"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793259471"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1186\/s40537-018-0115-x"},{"key":"e_1_3_2_1_13_1","volume-title":"Learning to index for nearest neighbor search","author":"Chiu Chih-Yi","year":"2019","unstructured":"Chih-Yi Chiu, Amorntip Prayoonwong, and Yin-Chih Liao. 2019. Learning to index for nearest neighbor search. IEEE transactions on pattern analysis and machine intelligence 42, 8 (2019), 1942\u20131956."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258655"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Kenneth L Clarkson et al. 2006. Nearest-neighbor searching and metric space dimensions. Nearest-neighbor methods for learning and vision: theory and practice (2006) 15\u201359.","DOI":"10.7551\/mitpress\/4908.003.0005"},{"key":"e_1_3_2_1_16_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms (3rd edition). MIT Press.","edition":"3"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335414"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1967.1053964"},{"key":"e_1_3_2_1_19_1","unstructured":"Ryan Ross Curtin. 2015. Improving dual-tree algorithms. Ph.D. Dissertation. Georgia Institute of Technology."},{"key":"e_1_3_2_1_20_1","unstructured":"Xiangyun Ding Rohin Garg Yan Gu and Yihan Sun. 2026. Parallel Metric Skip Lists and Nearest Neighbor Search. arXiv preprint arXiv:2606.03129."},{"key":"e_1_3_2_1_21_1","volume-title":"High-Performance and Flexible Parallel Algorithms for Semisort and Related Problems. arXiv preprint:2304.10078","author":"Dong Xiaojun","year":"2023","unstructured":"Xiaojun Dong, Yunshu Wu, Zhongqi Wang, Laxman Dhulipala, Yan Gu, and Yihan Sun. 2023. High-Performance and Flexible Parallel Algorithms for Semisort and Related Problems. arXiv preprint:2304.10078 (2023)."},{"key":"e_1_3_2_1_22_1","volume-title":"A new compressed cover tree guarantees a near linear parameterized complexity for all k-nearest neighbors search in metric spaces. arXiv preprint:2111.15478","author":"Elkin Yury","year":"2021","unstructured":"Yury Elkin and Vitaliy Kurlin. 2021. A new compressed cover tree guarantees a near linear parameterized complexity for all k-nearest neighbors search in metric spaces. arXiv preprint:2111.15478 (2021)."},{"key":"e_1_3_2_1_23_1","volume-title":"International Conference on Machine Learning. PMLR, 9267\u20139311","author":"Elkin Yury","year":"2023","unstructured":"Yury Elkin and Vitaliy Kurlin. 2023. A new near-linear time algorithm for k-nearest neighbor search using a compressed cover tree. In International Conference on Machine Learning. PMLR, 9267\u20139311."},{"key":"e_1_3_2_1_24_1","unstructured":"Martin Ester Hans-Peter Kriegel J\u00f6rg Sander and Xiaowei Xu. 1996. A Density-based Algorithm for Discovering Clusters a Density-based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. In KDD. 226\u2013231."},{"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","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2006.227"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICIP.2010.5654017"},{"key":"e_1_3_2_1_28_1","volume-title":"Statistical analysis of nearest neighbor methods for anomaly detection. Advances in Neural Information Processing Systems 32","author":"Gu Xiaoyi","year":"2019","unstructured":"Xiaoyi Gu, Leman Akoglu, and Alessandro Rinaldo. 2019. Statistical analysis of nearest neighbor methods for anomaly detection. Advances in Neural Information Processing Systems 32 (2019)."},{"key":"e_1_3_2_1_29_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_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3558481.3591069"},{"key":"e_1_3_2_1_31_1","volume-title":"Analysis of Work-Stealing and Parallel Cache Complexity. In SIAM Symposium on Algorithmic Principles of Computer Systems (APOCS). SIAM, 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). SIAM, 46\u201360."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490148.3538581"},{"key":"e_1_3_2_1_33_1","volume-title":"ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 24\u201334","author":"Gu Yan","unstructured":"Yan Gu, Julian Shun, Yihan Sun, and Guy E. Blelloch. 2015. A Top-Down Parallel Semisort. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 24\u201334."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.1"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_3_2_1_36_1","volume-title":"Optimization of indexing based on k-nearest neighbor graph for proximity search in high-dimensional data. arXiv preprint arXiv:1810.07355","author":"Iwasaki Masajiro","year":"2018","unstructured":"Masajiro Iwasaki and Daisuke Miyazaki. 2018. Optimization of indexing based on k-nearest neighbor graph for proximity search in high-dimensional data. arXiv preprint arXiv:1810.07355 (2018)."},{"key":"e_1_3_2_1_37_1","volume-title":"International Conference on Machine Learning (ICML). PMLR, 1162\u20131170","author":"Izbicki Mike","year":"2015","unstructured":"Mike Izbicki and Christian Shelton. 2015. Faster cover trees. In International Conference on Machine Learning (ICML). PMLR, 1162\u20131170."},{"key":"e_1_3_2_1_38_1","first-page":"547","article-title":"\u00c9tude comparative de la distribution florale dans une portion des Alpes et des Jura","volume":"37","author":"Jaccard Paul","year":"1901","unstructured":"Paul Jaccard. 1901. \u00c9tude comparative de la distribution florale dans une portion des Alpes et des Jura. Bull Soc Vaudoise Sci Nat 37 (1901), 547\u2013579.","journal-title":"Bull Soc Vaudoise Sci Nat"},{"key":"e_1_3_2_1_39_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_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510013"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.781637"},{"key":"e_1_3_2_1_42_1","volume-title":"ACM-SIAM Symposium on Discrete Algorithms (SODA). Citeseer, 798\u2013807","author":"Krauthgamer Robert","year":"2004","unstructured":"Robert Krauthgamer and James R Lee. 2004. Navigating nets: simple algorithms for proximity search. In ACM-SIAM Symposium on Discrete Algorithms (SODA). Citeseer, 798\u2013807."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2019.2909204"},{"key":"e_1_3_2_1_44_1","volume-title":"Wierzcho\u0144","author":"Luci\u0144ska Ma\u0142gorzata","year":"2012","unstructured":"Ma\u0142gorzata Luci\u0144ska and S\u0142awomir T. Wierzcho\u0144. 2012. Spectral Clustering Based on k-Nearest Neighbor Graph. In Computer Information Systems and Industrial Management. 254\u2013265."},{"key":"e_1_3_2_1_45_1","first-page":"49","article-title":"On the generalized distance in statistics","volume":"2","author":"Mahalanobis Prasanta Chandra","year":"1936","unstructured":"Prasanta Chandra Mahalanobis. 1936. On the generalized distance in statistics. Proceedings of the National Institute of Sciences of India 2, 1 (1936), 49\u201355.","journal-title":"Proceedings of the National Institute of Sciences of India"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.01.009"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3627535.3638475"},{"key":"e_1_3_2_1_48_1","volume-title":"Parallel Dynamic Spatial Indexes. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP). 150\u2013163","author":"Men Ziyang","year":"2026","unstructured":"Ziyang Men, Bo Huang, Yan Gu, and Yihan Sun. 2026. Parallel Dynamic Spatial Indexes. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP). 150\u2013163."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3709712"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICME.2009.5202635"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDMW.2015.62"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588908"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2022.08.047"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.1998.710701"},{"key":"e_1_3_2_1_55_1","unstructured":"Jan Matthias Ruhl. 2003. Efficient algorithms for new computational models. Ph.D. Dissertation. Massachusetts Institute of Technology."},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNN.2008.917504"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806907.1806912"},{"key":"e_1_3_2_1_58_1","volume-title":"Theoretically-Efficient and Practical Parallel DBSCAN. In ACM SIGMOD International Conference on Management of Data (SIGMOD). 2555\u20132571","author":"Wang Yiqiu","year":"2020","unstructured":"Yiqiu Wang, Yan Gu, and Julian Shun. 2020. Theoretically-Efficient and Practical Parallel DBSCAN. In ACM SIGMOD International Conference on Management of Data (SIGMOD). 2555\u20132571."},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457296"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2000824.2000825"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2006.886840"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.14778\/3489496.3489509"}],"event":{"name":"SPAA '26: 38th ACM Symposium on Parallelism in Algorithms and Architectures","location":"Royal Holloway, University of London London United Kingdom","acronym":"SPAA '26","sponsor":["SIGARCH ACM Special Interest Group on Computer Architecture","SIGACT ACM Special Interest Group on Algorithms and Computation Theory","EATCS"]},"container-title":["Proceedings of the 38th ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3816782.3819182","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T17:29:34Z","timestamp":1783531774000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3816782.3819182"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,6]]},"references-count":62,"alternative-id":["10.1145\/3816782.3819182","10.1145\/3816782"],"URL":"https:\/\/doi.org\/10.1145\/3816782.3819182","relation":{},"subject":[],"published":{"date-parts":[[2026,7,6]]},"assertion":[{"value":"2026-07-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}