HNSW
In plain wordsA popular way to organize millions of embeddings for fast similarity search: a layered web of links where the search starts with long jumps on sparse top layers, then takes ever shorter steps.
An approximate nearest neighborapproximate nearest neighbor search, n.: A family of shortcuts for finding the most similar items in a huge collection without checking every one — accepting an occasional miss in exchange for answers thousands of times faster. index made of stacked proximity graphs, from a dense bottom graph linking every stored vector to its near neighbors up to sparse top graphs holding a few vectors joined by long links. A query starts in the sparsest graph, hops greedily to whichever neighbor is nearer the query until none is, drops to the graph below and repeats, ending with a broader best-first search at the bottom; like changing from express to local trains, this needs only about logarithmically many hops. Each inserted vector draws a random top level, higher levels being exponentially rarer, and is linked to its nearest neighbors on every level up to it. Key parameters are M (links per node), efConstruction (candidate-list size while building) and efSearch (candidate-list size while querying, which trades speed for recallrecall@k, n.: A score for search systems: of all the right answers that exist, what fraction showed up in the top k results? Higher means fewer relevant items were missed.). HNSW offers some of the best speed–recall trade-offs for in-memory search and supports incremental inserts, but uses much RAM and handles deletions awkwardly; it is the default index in many vector databasesvector database, n.: A database built to store embeddings — lists of numbers that represent meaning — and to quickly find the stored items most similar to a new one. It is the memory behind many AI search tools..
We use HNSW with M = 32 for the hot index and a disk-based index for the archive.
Origin
Introduced by Yury Malkov and Dmitry Yashunin in 'Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs' (arXiv, March 2016; IEEE Transactions on Pattern Analysis and Machine Intelligence, online 2018, in print 2020), extending earlier flat navigable small world (NSW) graphs by Malkov and colleagues. The hnswlib library and adoption by Faiss, Lucene and vector databases made it ubiquitous.
Related
- approximate nearest neighbor searchapproximate nearest neighbor search, n.: A family of shortcuts for finding the most similar items in a huge collection without checking every one — accepting an occasional miss in exchange for answers thousands of times faster.
- vector searchvector search, n.: Searching by closeness instead of exact match: the query and all stored items are lists of numbers, and the search returns the items whose numbers are most similar to the query's.
- vector databasevector database, n.: A database built to store embeddings — lists of numbers that represent meaning — and to quickly find the stored items most similar to a new one. It is the memory behind many AI search tools.
- FAISSFAISS, prop. n.: A free software library from Meta for searching huge collections of embeddings very fast, on ordinary processors or graphics cards. Many AI search systems use it under the hood.
- product quantizationproduct quantization, n.: A compression trick for embeddings: chop each long list of numbers into short pieces and replace each piece with the ID of its closest typical piece, shrinking storage many times over while keeping search workable.
- recall@krecall@k, n.: A score for search systems: of all the right answers that exist, what fraction showed up in the top k results? Higher means fewer relevant items were missed.
Sources
- Malkov, Y. A. & Yashunin, D. A. (2020; online 2018). Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence 42(4): 824–836. arXiv:1603.09320. arxiv.org/abs/1603.09320v2
Mentioned in
approximate nearest neighbor searchapproximate nearest neighbor search, n.: A family of shortcuts for finding the most similar items in a huge collection without checking every one — accepting an occasional miss in exchange for answers thousands of times faster., FAISSFAISS, prop. n.: A free software library from Meta for searching huge collections of embeddings very fast, on ordinary processors or graphics cards. Many AI search systems use it under the hood., vector databasevector database, n.: A database built to store embeddings — lists of numbers that represent meaning — and to quickly find the stored items most similar to a new one. It is the memory behind many AI search tools., vector searchvector search, n.: Searching by closeness instead of exact match: the query and all stored items are lists of numbers, and the search returns the items whose numbers are most similar to the query's., locality-sensitive hashinglocality-sensitive hashing, n.: A trick for finding look-alikes in a huge collection without comparing every pair: items get short codes designed so that similar items tend to share a code, and only items sharing one are compared., product quantizationproduct quantization, n.: A compression trick for embeddings: chop each long list of numbers into short pieces and replace each piece with the ID of its closest typical piece, shrinking storage many times over while keeping search workable.