{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T09:42:49Z","timestamp":1775122969242,"version":"3.50.1"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:p>Nearest neighbor search (NNS) has a wide range of applications in information retrieval, computer vision, machine learning, databases, and other areas. Existing state-of-the-art algorithm for nearest neighbor search, Hierarchical Navigable Small World Networks (HNSW), is unable to scale to large datasets of 100M records in high dimensions. In this paper, we propose LANNS, an end-to-end platform for Approximate Nearest Neighbor Search, which scales for web-scale datasets. Library for Large Scale Approximate Nearest Neighbor Search (LANNS) is deployed in multiple production systems for identifying top-K (100 \u2264 k \u2264 200) approximate nearest neighbors with a latency of a few milliseconds per query, high throughput of ~2.5k Queries Per Second (QPS) on a single node, on large (e.g., ~ 180M data points) high dimensional (50-2048 dimensional) datasets.<\/jats:p>","DOI":"10.14778\/3503585.3503594","type":"journal-article","created":{"date-parts":[[2022,4,14]],"date-time":"2022-04-14T22:18:07Z","timestamp":1649974687000},"page":"850-858","source":"Crossref","is-referenced-by-count":13,"title":["LANNS"],"prefix":"10.14778","volume":"15","author":[{"given":"Ishita","family":"Doshi","sequence":"first","affiliation":[{"name":"LinkedIn"}]},{"given":"Dhritiman","family":"Das","sequence":"additional","affiliation":[{"name":"LinkedIn"}]},{"given":"Ashish","family":"Bhutani","sequence":"additional","affiliation":[{"name":"Uber"}]},{"given":"Rajeev","family":"Kumar","sequence":"additional","affiliation":[{"name":"LinkedIn"}]},{"given":"Rushi","family":"Bhatt","sequence":"additional","affiliation":[{"name":"Compass"}]},{"given":"Niranjan","family":"Balasubramanian","sequence":"additional","affiliation":[{"name":"LinkedIn"}]}],"member":"320","published-online":{"date-parts":[[2022,4,14]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188846"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746553"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/3204028.3204034"},{"key":"e_1_2_1_4_1","volume-title":"ANN benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms. CoRR abs \/","author":"Aumuller Martin","year":"1807","unstructured":"Martin Aumuller , Erik Bernhardsson , and Alexander John Faithfull . 2018. ANN benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms. CoRR abs \/ 1807 .05614 (2018), 1--20. arXiv:1807.05614 http:\/\/arxiv.org\/abs\/1807.05614 Martin Aumuller, Erik Bernhardsson, and Alexander John Faithfull. 2018. ANN benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms. CoRR abs \/ 1807.05614 (2018), 1--20. arXiv:1807.05614 http:\/\/arxiv.org\/abs\/1807.05614"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2014.2352458"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/98524.98564"},{"key":"e_1_2_1_7_1","volume-title":"Engineering Efficient and Effective Non-metric Space Library","author":"Boytsov Leonid","unstructured":"Leonid Boytsov and Bilegsaikhan Naidan . 2013. Engineering Efficient and Effective Non-metric Space Library . In Similarity Search and Applications, Nieves Brisaboa, Oscar Pedreira, and Pavel Zezula (Eds.). Springer Berlin Heidelberg , Berlin, Heidelberg , 280--293. Leonid Boytsov and Bilegsaikhan Naidan. 2013. Engineering Efficient and Effective Non-metric Space Library. In Similarity Search and Applications, Nieves Brisaboa, Oscar Pedreira, and Pavel Zezula (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 280--293."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1214\/ss\/1009213286"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9885-5"},{"key":"e_1_2_1_10_1","unstructured":"W. Dong. 2014. KGraph. Retrieved 24 June 2021 from https:\/\/github.com\/aaalgo\/kgraph  W. Dong. 2014. KGraph. Retrieved 24 June 2021 from https:\/\/github.com\/aaalgo\/kgraph"},{"key":"e_1_2_1_11_1","volume-title":"Optimized Product Quantization for Approximate Nearest Neighbor Search. In 2013 IEEE Conference on Computer Vision and Pattern Recognition. IEEE, USA, 2946--2953","author":"Ge T.","unstructured":"T. Ge , K. He , Q. Ke , and J. Sun . 2013 . Optimized Product Quantization for Approximate Nearest Neighbor Search. In 2013 IEEE Conference on Computer Vision and Pattern Recognition. IEEE, USA, 2946--2953 . T. Ge, K. He, Q. Ke, and J. Sun. 2013. Optimized Product Quantization for Approximate Nearest Neighbor Search. In 2013 IEEE Conference on Computer Vision and Pattern Recognition. IEEE, USA, 2946--2953."},{"key":"e_1_2_1_12_1","volume-title":"Distance Encoded Product Quantization. In 2014 IEEE Conference on Computer Vision and Pattern Recognition. IEEE, USA, 2139--2146","author":"Heo J.","unstructured":"J. Heo , Z. Lin , and S. Yoon . 2014 . Distance Encoded Product Quantization. In 2014 IEEE Conference on Computer Vision and Pattern Recognition. IEEE, USA, 2139--2146 . J. Heo, Z. Lin, and S. Yoon. 2014. Distance Encoded Product Quantization. In 2014 IEEE Conference on Computer Vision and Pattern Recognition. IEEE, USA, 2139--2146."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_2_1_14_1","volume-title":"Pruned Bi-directed K-nearest Neighbor Graph for Proximity Search","author":"Iwasaki Masajiro","unstructured":"Masajiro Iwasaki . 2016. Pruned Bi-directed K-nearest Neighbor Graph for Proximity Search . In Similarity Search and Applications, Laurent Amsaleg, Michael E. Houle, and Erich Schubert (Eds.). Springer International Publishing , Cham , 20--33. Masajiro Iwasaki. 2016. Pruned Bi-directed K-nearest Neighbor Graph for Proximity Search. In Similarity Search and Applications, Laurent Amsaleg, Michael E. Houle, and Erich Schubert (Eds.). Springer International Publishing, Cham, 20--33."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TBDATA.2019.2921572"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2010.57"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2014.298"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397240"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2013.10.006"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2018.2889473"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/3042573.3042779"},{"key":"e_1_2_1_22_1","unstructured":"L. McInnes. 2018. PyNNDescent. Retrieved 20 June 2021 from https:\/\/github.com\/lmcinnes\/pynndescent  L. McInnes. 2018. PyNNDescent. Retrieved 20 June 2021 from https:\/\/github.com\/lmcinnes\/pynndescent"},{"key":"e_1_2_1_23_1","first-page":"1","article-title":"MLlib: Machine Learning in Apache Spark","volume":"17","author":"Meng Xiangrui","year":"2016","unstructured":"Xiangrui Meng , Joseph Bradley , Burak Yavuz , Evan Sparks , Shivaram Venkataraman , Davies Liu , Jeremy Freeman , DB Tsai , Manish Amde , Sean Owen , Doris Xin , Reynold Xin , Michael J. Franklin , Reza Zadeh , Matei Zaharia , and Ameet Talwalkar . 2016 . MLlib: Machine Learning in Apache Spark . J. Mach. Learn. Res. 17 , 1 (Jan. 2016), 1235--1241. Xiangrui Meng, Joseph Bradley, Burak Yavuz, Evan Sparks, Shivaram Venkataraman, Davies Liu, Jeremy Freeman, DB Tsai, Manish Amde, Sean Owen, Doris Xin, Reynold Xin, Michael J. Franklin, Reza Zadeh, Matei Zaharia, and Ameet Talwalkar. 2016. MLlib: Machine Learning in Apache Spark. J. Mach. Learn. Res. 17, 1 (Jan. 2016), 1235--1241.","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_2_1_24_1","volume-title":"Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration. In VISAPP 2009 - Proceedings of the Fourth International Conference on Computer Vision Theory and Applications","volume":"1","author":"Muja Marius","year":"2009","unstructured":"Marius Muja and David G. Lowe . 2009 . Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration. In VISAPP 2009 - Proceedings of the Fourth International Conference on Computer Vision Theory and Applications , Lisboa, Portugal , February 5-8, 2009 - Volume 1 , Alpesh Ranchordas and Helder Ara\u00fajo (Eds.). INSTICC Press, Portugal, 331--340. Marius Muja and David G. Lowe. 2009. Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration. In VISAPP 2009 - Proceedings of the Fourth International Conference on Computer Vision Theory and Applications, Lisboa, Portugal, February 5-8, 2009 - Volume 1, Alpesh Ranchordas and Helder Ara\u00fajo (Eds.). INSTICC Press, Portugal, 331--340."},{"key":"e_1_2_1_25_1","unstructured":"Spotify. 2013. ANNOY library. https:\/\/github.com\/spotify\/annoy. Accessed: 2019-08-01.  Spotify. 2013. ANNOY library. https:\/\/github.com\/spotify\/annoy. Accessed: 2019-08-01."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 33rd International Conference on Neural Information Processing Systems. Curran Associates Inc.","author":"Subramanya Suhas Jayaram","year":"2019","unstructured":"Suhas Jayaram Subramanya , Devvrit, Rohan Kadekodi , Ravishankar Krishaswamy , and Harsha Vardhan Simhadri . 2019 . DiskANN: Fast Accurate Billion-Point Nearest Neighbor Search on a Single Node . In Proceedings of the 33rd International Conference on Neural Information Processing Systems. Curran Associates Inc. , Red Hook, NY, USA, Article 1233, 11 pages. Suhas Jayaram Subramanya, Devvrit, Rohan Kadekodi, Ravishankar Krishaswamy, and Harsha Vardhan Simhadri. 2019. DiskANN: Fast Accurate Billion-Point Nearest Neighbor Search on a Single Node. In Proceedings of the 33rd International Conference on Neural Information Processing Systems. Curran Associates Inc., Red Hook, NY, USA, Article 1233, 11 pages."},{"key":"e_1_2_1_27_1","unstructured":"Luca Trevisan. 2013. Lecture notes on expansion sparsest cut and spectral graph theory.  Luca Trevisan. 2013. Lecture notes on expansion sparsest cut and spectral graph theory."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/1795114.1795180"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the Twenty-Second Annual Conference on Neural Information Processing Systems","author":"Weiss Yair","year":"2008","unstructured":"Yair Weiss , Antonio Torralba , and Robert Fergus . 2008 . Spectral Hashing. In Advances in Neural Information Processing Systems 21 , Proceedings of the Twenty-Second Annual Conference on Neural Information Processing Systems , Vancouver, British Columbia, Canada , December 8-11, 2008, Daphne Koller, Dale Schuurmans, Yoshua Bengio, and L\u00e9on Bottou (Eds.). Curran Associates, Inc., Canada, 1753--1760. https:\/\/proceedings.neurips.cc\/paper\/2008\/hash\/d58072be2820e8682c0a27c0518e805e-Abstract.html Yair Weiss, Antonio Torralba, and Robert Fergus. 2008. Spectral Hashing. In Advances in Neural Information Processing Systems 21, Proceedings of the Twenty-Second Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 8-11, 2008, Daphne Koller, Dale Schuurmans, Yoshua Bengio, and L\u00e9on Bottou (Eds.). Curran Associates, Inc., Canada, 1753--1760. https:\/\/proceedings.neurips.cc\/paper\/2008\/hash\/d58072be2820e8682c0a27c0518e805e-Abstract.html"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2934664"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00094"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3503585.3503594","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:28:17Z","timestamp":1672223297000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3503585.3503594"}},"subtitle":["a web-scale approximate nearest neighbor lookup system"],"short-title":[],"issued":{"date-parts":[[2021,12]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["10.14778\/3503585.3503594"],"URL":"https:\/\/doi.org\/10.14778\/3503585.3503594","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2021,12]]}}}