{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,16]],"date-time":"2025-10-16T20:56:36Z","timestamp":1760648196679,"version":"3.41.0"},"reference-count":63,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"name":"NSF","award":["OAC 22042261"],"award-info":[{"award-number":["OAC 22042261"]}]},{"name":"Cooperative Agreement","award":["2421782"],"award-info":[{"award-number":["2421782"]}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"crossref","award":["MPS-AI-00010515"],"award-info":[{"award-number":["MPS-AI-00010515"]}],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"crossref"}]},{"name":"U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, Applied Mathematics program, Mathematical Multifaceted Integrated Capability Centers","award":["DE-SC0023171"],"award-info":[{"award-number":["DE-SC0023171"]}]},{"name":"U.S. Department of Energy, National Nuclear Security Administration","award":["DE-NA0003969"],"award-info":[{"award-number":["DE-NA0003969"]}]},{"DOI":"10.13039\/100000049","name":"U.S. National Institute on Aging","doi-asserted-by":"crossref","award":["R21AG074276-01"],"award-info":[{"award-number":["R21AG074276-01"]}],"id":[{"id":"10.13039\/100000049","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2025,9,30]]},"abstract":"<jats:p>\n            Constructing k-nearest neighbor (kNN) graphs is a fundamental component in many machine learning and scientific computing applications. Despite its prevalence, efficiently building all-nearest-neighbor graphs at scale on distributed heterogeneous HPC systems remains challenging, especially for large sparse non-integer datasets. We introduce optimizations for algorithms based on forests of random projection trees. Our novel GPU kernels for batched, within leaf, exact searches achieve 1.18\u00d7 speedup over sparse reference kernels with less peak memory, and up to 19\u00d7 speedup over CPU for memory-intensive problems. Our library,\n            <jats:monospace>PyRKNN<\/jats:monospace>\n            , implements distributed randomized projection forests for approximate kNN search. Optimizations to reduce and hide communication overhead allow us to achieve 5\u00d7 speedup, in per iteration performance, relative to GOFMM (another projection tree, MPI-based kNN library), for a 64M 128d dataset on 1,024 processes. On a single-node we achieve speedup over FAISS-GPU for dense datasets and up to 10\u00d7 speedup over CPU-only libraries.\n            <jats:monospace>PyRKNN<\/jats:monospace>\n            uniquely supports distributed memory kNN graph construction for both dense and sparse coordinates on CPU and GPU accelerators.\n          <\/jats:p>","DOI":"10.1145\/3733610","type":"journal-article","created":{"date-parts":[[2025,4,30]],"date-time":"2025-04-30T11:27:46Z","timestamp":1746012466000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Scalable KNN Graph Construction for Heterogeneous Architectures"],"prefix":"10.1145","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5702-022X","authenticated-orcid":false,"given":"William","family":"Ruys","sequence":"first","affiliation":[{"name":"Oden Institute, The University of Texas at Austin, Austin, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3345-4685","authenticated-orcid":false,"given":"Ali","family":"Ghafouri","sequence":"additional","affiliation":[{"name":"Oden Institute, The University of Texas at Austin, Austin, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5385-3651","authenticated-orcid":false,"given":"Chao","family":"Chen","sequence":"additional","affiliation":[{"name":"Department of Mathematics, North Carolina State University, Raleigh, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0033-3994","authenticated-orcid":false,"given":"George","family":"Biros","sequence":"additional","affiliation":[{"name":"Oden Institute, The University of Texas at Austin, Austin, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,14]]},"reference":[{"key":"e_1_3_2_2_2","first-page":"420","volume-title":"International Conference on Database Theory","author":"Aggarwal Charu C","year":"2001","unstructured":"Charu C Aggarwal, Alexander Hinneburg, and Daniel A Keim. 2001. On the surprising behavior of distance metrics in high dimensional space. In International Conference on Database Theory. Springer, 420\u2013434."},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/0908055"},{"key":"e_1_3_2_4_2","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1109\/FOCS.2006.49","volume-title":"2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201906)","author":"Andoni Alexandr","year":"2006","unstructured":"Alexandr Andoni and Piotr Indyk. 2006. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201906). IEEE, 459\u2013468."},{"key":"e_1_3_2_5_2","doi-asserted-by":"crossref","first-page":"793","DOI":"10.1145\/2746539.2746553","volume-title":"Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing","author":"Andoni Alexandr","year":"2015","unstructured":"Alexandr Andoni and Ilya Razenshteyn. 2015. Optimal data-dependent hashing for approximate near neighbors. In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing. ACM, Portland Oregon USA, 793\u2013801. DOI:10.1145\/2746539.2746553"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/304181.304187"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","unstructured":"Martin Aum\u00fcller Erik Bernhardsson and Alexander Faithfull. 2020. ANN-benchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Information Systems 87 (2020) 101374. 10.1016\/j.is.2019.02.006","DOI":"10.1016\/j.is.2019.02.006"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2021.101807"},{"key":"e_1_3_2_9_2","unstructured":"Sergey Brin. 1995. Near neighbor search in large metric spaces. In Proceedings of the 21th International Conference on Very Large Data Bases (VLDB\u201995). Morgan Kaufmann Publishers Inc. San Francisco CA USA 574\u2013584."},{"key":"e_1_3_2_10_2","unstructured":"Deng Cai Xiuye Gu and Chaoqi Wang. 2017. A revisit on deep hashings for large-scale content based image retrieval. arXiv preprint arXiv:1711.06016 (2017). http:\/\/www.cad.zju.edu.cn\/home\/dengcai\/Data\/ANNS\/ANNSData.html"},{"key":"e_1_3_2_11_2","volume-title":"SPTAG: A Library for Fast Approximate Nearest Neighbor Search","author":"Chen Qi","year":"2018","unstructured":"Qi Chen, Haidong Wang, Mingqin Li, Gang Ren, Scarlett Li, Jeffery Zhu, Jason Li, Chuanjie Liu, Lintao Zhang, and Jingdong Wang. 2018. SPTAG: A Library for Fast Approximate Nearest Neighbor Search. Retrieved from https:\/\/github.com\/Microsoft\/SPTAG"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10745-0_1"},{"key":"e_1_3_2_13_2","first-page":"537","volume-title":"Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing","author":"Dasgupta Sanjoy","year":"2008","unstructured":"Sanjoy Dasgupta and Yoav Freund. 2008. Random projection trees and low dimensional manifolds. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing. 537\u2013546."},{"key":"e_1_3_2_14_2","first-page":"317","volume-title":"Conference on Learning Theory","author":"Dasgupta Sanjoy","year":"2013","unstructured":"Sanjoy Dasgupta and Kaushik Sinha. 2013. Randomized partition trees for exact nearest neighbor search. In Conference on Learning Theory. PMLR, 317\u2013337."},{"issue":"6","key":"e_1_3_2_15_2","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1109\/MSP.2012.2211477","article-title":"The mnist database of handwritten digit images for machine learning research","volume":"29","author":"Deng Li","year":"2012","unstructured":"Li Deng. 2012. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine 29, 6 (2012), 141\u2013142.","journal-title":"IEEE Signal Processing Magazine"},{"key":"e_1_3_2_16_2","doi-asserted-by":"crossref","first-page":"1066","DOI":"10.1109\/BigData47090.2019.9006219","volume-title":"2019 IEEE International Conference on Big Data (Big Data)","author":"Deng Shiyuan","year":"2019","unstructured":"Shiyuan Deng, Xiao Yan, K.W. Ng Kelvin, Chenyu Jiang, and James Cheng. 2019. Pyramid: A general framework for distributed similarity search on large-scale datasets. In 2019 IEEE International Conference on Big Data (Big Data). 1066\u20131071. DOI:10.1109\/BigData47090.2019.9006219"},{"key":"e_1_3_2_17_2","doi-asserted-by":"crossref","first-page":"577","DOI":"10.1145\/1963405.1963487","volume-title":"Proceedings of the 20th International Conference on World Wide Web (WWW \u201911)","author":"Dong Wei","year":"2011","unstructured":"Wei Dong, Charikar Moses, and Kai Li. 2011. Efficient k-nearest neighbor graph construction for generic similarity measures. In Proceedings of the 20th International Conference on World Wide Web (WWW \u201911). Association for Computing Machinery, New York, NY, USA, 577\u2013586. DOI:10.1145\/1963405.1963487"},{"key":"e_1_3_2_18_2","unstructured":"Dheeru Dua and Casey Graff. 2017. UCI Machine Learning Repository. (2017). Retrieved from http:\/\/archive.ics.uci.edu\/ml"},{"key":"e_1_3_2_19_2","volume-title":"The Elements of Statistical Learning","author":"Friedman Jerome","year":"2001","unstructured":"Jerome Friedman, Trevor Hastie, and Robert Tibshirani. 2001. The Elements of Statistical Learning. Vol. 1. Springer series in statistics New York."},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","unstructured":"Lars Gottesb\u00fcren Laxman Dhulipala Rajesh Jayaram and Jakub Lacki. 2024. Unleashing Graph Partitioning for Large-Scale Nearest Neighbor Search. (March2024). DOI:10.48550\/arXiv.2403.01797arxiv:cs\/2403.01797","DOI":"10.48550\/arXiv.2403.01797"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","unstructured":"Fabian Groh Lukas Ruppert Patrick Wieschollek and Hendrik P. A. Lensch. 2023. GGNN: Graph-based GPU nearest neighbor search. IEEE Transactions on Big Data 9 1 (2023) 267\u2013279. 10.1109\/TBDATA.2022.3161156","DOI":"10.1109\/TBDATA.2022.3161156"},{"key":"e_1_3_2_22_2","volume-title":"International Conference on Machine Learning","author":"Guo Ruiqi","year":"2020","unstructured":"Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar. 2020. Accelerating large-scale inference with anisotropic vector quantization. In International Conference on Machine Learning. Retrieved from https:\/\/arxiv.org\/abs\/1908.10396"},{"issue":"1","key":"e_1_3_2_23_2","doi-asserted-by":"crossref","first-page":"321","DOI":"10.4086\/toc.2012.v008a014","article-title":"Approximate nearest neighbor: Towards removing the curse of dimensionality","volume":"8","author":"Har-Peled Sariel","year":"2012","unstructured":"Sariel Har-Peled, Piotr Indyk, and Rajeev Motwani. 2012. Approximate nearest neighbor: Towards removing the curse of dimensionality. Theory of Computing 8, 1 (2012), 321\u2013350.","journal-title":"Theory of Computing"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/366622.366647"},{"key":"e_1_3_2_25_2","doi-asserted-by":"crossref","first-page":"881","DOI":"10.1109\/BigData.2016.7840682","volume-title":"2016 IEEE International Conference on Big Data (Big Data)","author":"Hyv\u00f6nen Ville","year":"2016","unstructured":"Ville Hyv\u00f6nen, Teemu Pitk\u00e4nen, Sotiris Tasoulis, Elias J\u00e4\u00e4saari, Risto Tuomainen, Liang Wang, Jukka Corander, and Teemu Roos. 2016. Fast nearest neighbor search through sparse random projections and voting. In 2016 IEEE International Conference on Big Data (Big Data). IEEE, 881\u2013888."},{"key":"e_1_3_2_26_2","doi-asserted-by":"crossref","first-page":"604","DOI":"10.1145\/276698.276876","volume-title":"Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing","author":"Indyk Piotr","year":"1998","unstructured":"Piotr Indyk and Rajeev Motwani. 1998. Approximate nearest neighbors: Towards removing the curse of dimensionality. In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing. 604\u2013613."},{"key":"e_1_3_2_27_2","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)."},{"issue":"8","key":"e_1_3_2_28_2","doi-asserted-by":"crossref","first-page":"651","DOI":"10.1016\/j.patrec.2009.09.011","article-title":"Data clustering: 50 years beyond k-means","volume":"31","author":"Jain Anil K","year":"2010","unstructured":"Anil K Jain. 2010. Data clustering: 50 years beyond k-means. Pattern Recognition Letters 31, 8 (2010), 651\u2013666.","journal-title":"Pattern Recognition Letters"},{"issue":"1","key":"e_1_3_2_29_2","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1109\/TPAMI.2010.57","article-title":"Product quantization for nearest neighbor search","volume":"33","author":"Jegou Herve","year":"2010","unstructured":"Herve Jegou, Matthijs Douze, and Cordelia Schmid. 2010. Product quantization for nearest neighbor search. IEEE Transactions on Pattern Analysis and Machine Intelligence 33, 1 (2010), 117\u2013128.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"e_1_3_2_30_2","volume-title":"Proceedings of the 36th ACM International Conference on Supercomputing (ICS \u201922)","author":"Ji Zhuoran","year":"2022","unstructured":"Zhuoran Ji and Cho-Li Wang. 2022. Efficient exact k-nearest neighbor graph construction for billion-scale datasets using GPUs with tensor cores. In Proceedings of the 36th ACM International Conference on Supercomputing (ICS \u201922). Association for Computing Machinery, New York, NY, USA, Article 10, 12 pages. DOI:10.1145\/3524059.3532368"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","unstructured":"Jeff Johnson Matthijs Douze and Herv\u00e9 J\u00e9gou. 2021. Billion-scale similarity search with GPUs. IEEE Transactions on Big Data 7 3 (2021) 535\u2013547. 10.1109\/TBDATA.2019.2921572","DOI":"10.1109\/TBDATA.2019.2921572"},{"issue":"38","key":"e_1_3_2_32_2","doi-asserted-by":"crossref","first-page":"15679","DOI":"10.1073\/pnas.1107769108","article-title":"Randomized approximate nearest neighbors algorithm","volume":"108","author":"Jones Peter Wilcox","year":"2011","unstructured":"Peter Wilcox Jones, Andrei Osipov, and Vladimir Rokhlin. 2011. Randomized approximate nearest neighbors algorithm. Proceedings of the National Academy of Sciences 108, 38 (2011), 15679\u201315686.","journal-title":"Proceedings of the National Academy of Sciences"},{"issue":"1","key":"e_1_3_2_33_2","first-page":"185","article-title":"On the number of comparisons in hoare\u2019s algorithm FIND","volume":"33","author":"Kodaj B","year":"1997","unstructured":"B Kodaj and TF M\u00f3ri. 1997. On the number of comparisons in hoare\u2019s algorithm FIND. Studia Scientiarum Mathematicarum Hungarica 33, 1 (1997), 185\u2013208.","journal-title":"Studia Scientiarum Mathematicarum Hungarica"},{"key":"e_1_3_2_34_2","unstructured":"Thijs Laarhoven. 2018. Graph-based time-space trade-offs for approximate near neighbors. arXiv:1712.03158. Retrieved from https:\/\/arxiv.org\/abs\/1712.03158"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1017\/jpr.2020.21"},{"issue":"4","key":"e_1_3_2_36_2","doi-asserted-by":"crossref","first-page":"824","DOI":"10.1109\/TPAMI.2018.2889473","article-title":"Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs","volume":"42","author":"Malkov Yu A","year":"2018","unstructured":"Yu A Malkov and Dmitry A Yashunin. 2018. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence 42, 4 (2018), 824\u2013836. Retrieved from https:\/\/github.com\/nmslib\/nmslib","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"e_1_3_2_37_2","unstructured":"Leland McInnes. 2024. PyNNDescent Nov. 2024. vcs: https:\/\/github.com\/lmcinnes\/pynndescent swhid: \\(\\langle\\) swh:1:dir:2c196580751fedb17c7aa6a2de0339546af7cf8a \\(\\rangle\\) ."},{"key":"e_1_3_2_38_2","unstructured":"Nicholas Meisburger and Anshumali Shrivastava. 2020. Distributed tera-scale similarity search with mpi: Provably efficient similarity search over billions without a single distance computation. arXiv preprint arXiv:2008.03260 (2020)."},{"key":"e_1_3_2_39_2","first-page":"1","volume-title":"50th International Conference on Parallel Processing Workshop (ICPP Workshops \u201921)","author":"Meyer Bruno","year":"2021","unstructured":"Bruno Meyer, Aurora Pozo, and Wagner M. Nunan Zola. 2021. Warp-centric k-nearest neighbor graphs construction on GPU. In 50th International Conference on Parallel Processing Workshop (ICPP Workshops \u201921). Association for Computing Machinery, New York, NY, USA, 1\u201310. DOI:10.1145\/3458744.3474053"},{"key":"e_1_3_2_40_2","unstructured":"Francesco Mezzadri. 2006. How to generate random matrices from the classical compact groups. arXiv preprint math-ph\/0609050 (2006)."},{"issue":"11","key":"e_1_3_2_41_2","doi-asserted-by":"crossref","first-page":"2227","DOI":"10.1109\/TPAMI.2014.2321376","article-title":"Scalable nearest neighbor algorithms for high dimensional data","volume":"36","author":"Muja Marius","year":"2014","unstructured":"Marius Muja and David G Lowe. 2014. Scalable nearest neighbor algorithms for high dimensional data. Pattern Analysis and Machine Intelligence, IEEE Transactions on 36, 11 (2014), 2227\u20132240. Retrieved from https:\/\/github.com\/mariusmuja\/flann","journal-title":"Pattern Analysis and Machine Intelligence, IEEE Transactions on"},{"key":"e_1_3_2_42_2","unstructured":"Corey J. Nolet Divye Gala Edward Raff Joe Eaton Brad Rees John Zedlewski and Tim Oates. 2022. GPU semiring primitives for sparse neighborhood methods. Proceedings of Machine Learning and Systems 4 (2022) 95\u2013109."},{"key":"e_1_3_2_43_2","first-page":"211","volume-title":"Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS \u201911)","author":"Pan Jia","year":"2011","unstructured":"Jia Pan and Dinesh Manocha. 2011. Fast GPU-based locality sensitive hashing for k-nearest neighbor computation. In Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS \u201911). Association for Computing Machinery, New York, NY, USA, 211\u2013220. DOI:10.1145\/2093973.2094002"},{"key":"e_1_3_2_44_2","unstructured":"Nicolas Papernot and Patrick McDaniel. 2018. Deep k-nearest neighbors: Towards confident interpretable and robust deep learning. arXiv:1803.04765. Retrieved from https:\/\/arxiv.org\/abs\/1803.04765"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2016.57"},{"key":"e_1_3_2_46_2","first-page":"1532","volume-title":"Empirical Methods in Natural Language Processing (EMNLP)","author":"Pennington Jeffrey","year":"2014","unstructured":"Jeffrey Pennington, Richard Socher, and Christopher D. Manning. 2014. GloVe: Global vectors for word representation. In Empirical Methods in Natural Language Processing (EMNLP). 1532\u20131543. Retrieved from http:\/\/www.aclweb.org\/anthology\/D14-1162"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","unstructured":"Aleksandra Piktus Fabio Petroni Vladimir Karpukhin Dmytro Okhonko Samuel Broscheit Gautier Izacard Patrick Lewis Barlas O\u011fuz Edouard Grave Wen-tau Yih and Sebastian Riedel. 2022. The Web Is Your Oyster - Knowledge-Intensive NLP against a Very Large Web Corpus. (May2022). DOI:10.48550\/arXiv.2112.09924","DOI":"10.48550\/arXiv.2112.09924"},{"key":"e_1_3_2_48_2","unstructured":"Liudmila Prokhorenkova and Aleksandr Shekhovtsov. 2020. Graph-based nearest neighbor search: from practice to theory. In Proceedings of the 37th International Conference on Machine Learning (ICML\u201920). Article 723 JMLR.org."},{"key":"e_1_3_2_49_2","first-page":"1378","volume-title":"Proceedings of the 25th acm Sigkdd International Conference on Knowledge Discovery & Data Mining","author":"Ram Parikshit","year":"2019","unstructured":"Parikshit Ram and Kaushik Sinha. 2019. Revisiting kd-tree for nearest neighbor search. In Proceedings of the 25th acm Sigkdd International Conference on Knowledge Discovery & Data Mining. 1378\u20131388."},{"key":"e_1_3_2_50_2","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1109\/CLUSTER49012.2020.00040","volume-title":"2020 IEEE International Conference on Cluster Computing (CLUSTER)","author":"Bashyam K G Renga","year":"2020","unstructured":"K G Renga Bashyam and Sathish Vadhiyar. 2020. Fast scalable approximate nearest neighbor search for high-dimensional data. In 2020 IEEE International Conference on Cluster Computing (CLUSTER). 294\u2013302. DOI:10.1109\/CLUSTER49012.2020.00040ISSN: 2168-9253."},{"issue":"12","key":"e_1_3_2_51_2","doi-asserted-by":"crossref","first-page":"124116","DOI":"10.1063\/1.3569857","article-title":"Determination of reaction coordinates via locally scaled diffusion map","volume":"134","author":"Rohrdanz Mary A","year":"2011","unstructured":"Mary A Rohrdanz, Wenwei Zheng, Mauro Maggioni, and Cecilia Clementi. 2011. Determination of reaction coordinates via locally scaled diffusion map. The Journal of Chemical Physics 134, 12 (2011), 124116.","journal-title":"The Journal of Chemical Physics"},{"key":"e_1_3_2_52_2","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1109\/ICMLA.2014.13","volume-title":"2014 13th International Conference on Machine Learning and Applications","author":"Sinha Kaushik","year":"2014","unstructured":"Kaushik Sinha. 2014. LSH vs randomized partition trees: Which one to use for nearest neighbor search?. In 2014 13th International Conference on Machine Learning and Applications. 41\u201346. DOI:10.1109\/ICMLA.2014.13"},{"key":"e_1_3_2_53_2","first-page":"681","volume-title":"Artificial Intelligence and Statistics","author":"Sinha Kaushik","year":"2017","unstructured":"Kaushik Sinha and Omid Keivani. 2017. Sparse randomized partition trees for nearest neighbor search. In Artificial Intelligence and Statistics. PMLR, 681\u2013689."},{"key":"e_1_3_2_54_2","doi-asserted-by":"crossref","unstructured":"Rainer Storn and Kenneth Price. 1997. Differential evolution.a simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization 11 (1997) 341\u2013359.","DOI":"10.1023\/A:1008202821328"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90074-R"},{"key":"e_1_3_2_56_2","first-page":"48","volume-title":"IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) (Leibniz International Proceedings in Informatics (LIPIcs))","volume":"18","author":"Vempala Santosh S.","year":"2012","unstructured":"Santosh S. Vempala. 2012. Randomly-oriented k-d trees adapt to intrinsic dimension. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) (Leibniz International Proceedings in Informatics (LIPIcs)), Deepak D\u2019Souza, Jaikumar Radhakrishnan, and Kavitha Telikepalli (Eds.), Vol. 18. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 48\u201357. DOI:10.4230\/LIPIcs.FSTTCS.2012.48"},{"key":"e_1_3_2_57_2","doi-asserted-by":"crossref","first-page":"1929","DOI":"10.1145\/3459637.3482344","volume-title":"Proceedings of the 30th ACM International Conference on Information & Knowledge Management","author":"Wang Hui","year":"2021","unstructured":"Hui Wang, Wan-Lei Zhao, Xiangxiang Zeng, and Jianye Yang. 2021. Fast k-NN graph construction by GPU based NN-descent. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management. Association for Computing Machinery, New York, NY, USA, 1929\u20131938. DOI:10.1145\/3459637.3482344"},{"key":"e_1_3_2_58_2","doi-asserted-by":"crossref","first-page":"889","DOI":"10.1145\/3183713.3196925","volume-title":"Proceedings of the 2018 International Conference on Management of Data","author":"Wang Yiqiu","year":"2018","unstructured":"Yiqiu Wang, Anshumali Shrivastava, Jonathan Wang, and Junghee Ryu. 2018. Randomized algorithms accelerated over cpu-gpu for ultra-high dimensional similarity search. In Proceedings of the 2018 International Conference on Management of Data. 889\u2013903. Retrieved from https:\/\/github.com\/RUSH-LAB\/Flash"},{"issue":"5","key":"e_1_3_2_59_2","first-page":"S667\u2013S699","article-title":"Parallel algorithms for nearest neighbor search problems in high dimensions","volume":"38","author":"Xiao Bo","year":"2016","unstructured":"Bo Xiao and George Biros. 2016. Parallel algorithms for nearest neighbor search problems in high dimensions. SIAM Journal on Scientific Computing 38, 5 (2016), S667\u2013S699.","journal-title":"SIAM Journal on Scientific Computing"},{"key":"e_1_3_2_60_2","first-page":"1","volume-title":"Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis","author":"Yu Chenhan D","year":"2015","unstructured":"Chenhan D Yu, Jianyu Huang, Woody Austin, Bo Xiao, and George Biros. 2015. Performance optimization for the k-nearest neighbors kernel on x86 architectures. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. 1\u201312."},{"key":"e_1_3_2_61_2","volume-title":"Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis (SC \u201918)","author":"Yu Chenhan D.","year":"2018","unstructured":"Chenhan D. Yu, Severin Reiz, and George Biros. 2018. Distributed-memory hierarchical compression of dense SPD matrices. In Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis (SC \u201918). IEEE Press, Piscataway, NJ, USA, Article 15, 15 pages. Retrieved from https:\/\/dl.acm.org\/citation.cfm?id=3291676"},{"key":"e_1_3_2_62_2","unstructured":"Chenhan D. Yu Severin Riesz and James Levitt. 2021. The University of Texas at Austin. vcs: https:\/\/github.com\/ChenhanYu\/hmlp swhid: \\(\\langle\\) swh:1:rev:8a3256e53ff8419530c6851ecbef1f4625f6c37f \\(\\rangle\\) ."},{"key":"e_1_3_2_63_2","first-page":"1033","volume-title":"36th IEEE International Conference on Data Engineering, ICDE 2020, Dallas, TX, USA, April 20-24, 2020","author":"Zhao Weijie","year":"2020","unstructured":"Weijie Zhao, Shulong Tan, and Ping Li. 2020. SONG: Approximate nearest neighbor search on GPU. In 36th IEEE International Conference on Data Engineering, ICDE 2020, Dallas, TX, USA, April 20-24, 2020. IEEE, 1033\u20131044."},{"key":"e_1_3_2_64_2","doi-asserted-by":"publisher","unstructured":"Wan-Lei Zhao Hui Wang Peng-Cheng Lin and Chong-Wah Ngo. 2022. On the merge of k-NN graph. IEEE Transactions on Big Data 8 6 (2022) 1496\u20131510. 10.1109\/TBDATA.2021.3101517","DOI":"10.1109\/TBDATA.2021.3101517"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3733610","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,14]],"date-time":"2025-06-14T12:01:39Z","timestamp":1749902499000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3733610"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,14]]},"references-count":63,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,9,30]]}},"alternative-id":["10.1145\/3733610"],"URL":"https:\/\/doi.org\/10.1145\/3733610","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"type":"print","value":"2329-4949"},{"type":"electronic","value":"2329-4957"}],"subject":[],"published":{"date-parts":[[2025,6,14]]},"assertion":[{"value":"2024-10-17","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-04-13","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-06-14","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}