Repository files navigation

• NMSLIB is generic but fast.
• A history of creation of the library is covered inthis episode of the Vector Podcast.
• A standalone implementation of our fastest method HNSWalso exists as a header-only library.
• We provide binaries for Python 3.8-3.13 (also 3.14 for Linux) for three OS (Linux, MacOS, Windows) and two types of CPU (Intel, ARM).
• All the documentation (including usingPython bindings and the query server, description of methods and spaces, building the library, etc) can be foundon this page.
• Forgeneric questions/inquiries, please, usethe Gitter chat: GitHub issues page is for bugs and feature requests.

Non-Metric Space Library (NMSLIB) is anefficient cross-platform similarity search library and a toolkit for evaluation of similarity search methods. The core-library doesnot have any third-party dependencies. It has been gaining popularity recently. In particular, it has become a part ofAmazon Elasticsearch Service.

The goal of the project is to create an effective andcomprehensive toolkit for searching ingeneric and non-metric spaces.Even though the library contains a variety of metric-space access methods,our main focus is ongeneric andapproximate search methods,in particular, on methods for non-metric spaces.NMSLIB is possibly the first library with a principled support for non-metric space searching.

NMSLIB is anextendible library, which means that is possible to add new search methods and distance functions. NMSLIB can be used directly in C++ and Python (via Python bindings). In addition, it is also possible to build a query server, which can be used from Java (or other languages supported by Apache Thrift (version 0.12). Java has a native client, i.e., it works on many platforms without requiring a C++ library to be installed.

Authors: Bilegsaikhan Naidan, Leonid Boytsov, Yury Malkov, David Novak.With contributions from Ben Frederickson, Lawrence Cayton, Wei Dong, Avrelin Nikita, Dmitry Yashunin, Bob Poekert, @orgoro, @gregfriedland,Scott Gigante, Maxim Andreev, Daniel Lemire, Nathan Kurz, Alexander Ponomarenko.

NMSLIB started as a personal project of Bilegsaikhan Naidan, who created the initial code base, the Python bindings, and participated in earlier evaluations.The most successful class of methods--neighborhood/proximity graphs--is represented by the Hierarchical Navigable Small World Graph (HNSW) due to Malkov and Yashunin (see the publications below). Other most useful methods, include a modification of the VP-tree due to Boytsov and Naidan (2013), a Neighborhood APProximation index (NAPP) proposed by Tellez et al. (2013) and improved by David Novak, as well as a vanilla uncompressed inverted file.The history of NMSLIB is also covered inthis episode of the Vector Podcast

If you find this library useful, feel free to cite our SISAP paper[BibTex] as well as other papers listed in the end. Onecrucial contribution to cite is the fast Hierarchical Navigable World graph (HNSW) method[BibTex]. Please,also check out the stand-alone HNSW implementation by Yury Malkov, which is released as a header-only HNSWLib library.

The code is released under the Apache License Version 2.0http://www.apache.org/licenses/.Older versions of the library include additional components, which have different licenses (but this does not apply to NMLISB 2.x):

Older versions of the library included the following components:

• The LSHKIT, which is embedded in our library, is distributed under the GNU General Public License, seehttp://www.gnu.org/licenses/.
• The k-NN graph construction algorithmNN-Descent due to Dong et al. 2011 (see the links below), which is also embedded in our library, seems to be covered by a free-to-use license, similar to Apache 2.
• FALCONN library's licence is MIT.

Leonid Boytsov was supported by theOpen Advancement of Question Answering Systems (OAQA) group and the following NSF grant #1618159: "Matching and Ranking via Proximity Graphs: Applications to Question Answering and Beyond". Bileg was supported by theiAd Center.

Most important related papers are listed below in the chronological order:

• L. Boytsov, D. Novak, Y. Malkov, E. Nyberg (2016).Off the Beaten Path: Let’s Replace Term-Based Retrievalwith k-NN Search. In proceedings of CIKM'16.[BibTex] We use a special branch of this library, plusthe following Java code.
• Malkov, Y.A., Yashunin, D.A.. (2016).Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs. CoRR, abs/1603.09320.[BibTex]
• Bilegsaikhan, N., Boytsov, L. 2015Permutation Search Methods are Efficient, Yet Faster Search is Possible PVLDB, 8(12):1618--1629, 2015[BibTex]
• Ponomarenko, A., Averlin, N., Bilegsaikhan, N., Boytsov, L., 2014.Comparative Analysis of Data Structures for Approximate Nearest Neighbor Search.[BibTex]
• Malkov, Y., Ponomarenko, A., Logvinov, A., & Krylov, V., 2014.Approximate nearest neighbor algorithm based on navigable small world graphs. Information Systems, 45, 61-68.[BibTex]
• Boytsov, L., Bilegsaikhan, N., 2013.Engineering Efficient and Effective Non-Metric Space Library. In Proceedings of the 6th International Conference on Similarity Search and Applications (SISAP 2013).[BibTex]
• Boytsov, L., Bilegsaikhan, N., 2013.Learning to Prune in Metric and Non-Metric Spaces. In Advances in Neural Information Processing Systems 2013.[BibTex]
• Tellez, Eric Sadit, Edgar Chávez, and Gonzalo Navarro.Succinct nearest neighbor search. Information Systems 38.7 (2013): 1019-1030.[BibTex]
• A. Ponomarenko, Y. Malkov, A. Logvinov, and V. KrylovApproximate nearestneighbor search small world approach. ICTA 2011
• Dong, Wei, Charikar Moses, and Kai Li. 2011.Efficient k-nearest neighbor graph construction for generic similarity measures. Proceedings of the 20th international conference on World wide web. ACM, 2011.[BibTex]
• L. Cayton, 2008Fast nearest neighbor retrieval for bregman divergences. Twenty-Fifth International Conference on Machine Learning (ICML).[BibTex]
• Amato, Giuseppe, and Pasquale Savino. 2008 Approximate similarity search in metric spaces using inverted files.[BibTex]
• Gonzalez, Edgar Chavez, Karina Figueroa, and Gonzalo Navarro.Effective proximity retrieval by ordering permutations. Pattern Analysis and Machine Intelligence, IEEE Transactions on 30.9 (2008): 1647-1658.[BibTex]