approximate nearest neighbor search
In plain wordsA 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.
A class of algorithms and index structures that return points close to a query — usually the top k under some distance — without comparing the query with every stored point, accepting that some true nearest neighbors may be missed. Formally, a (1+ε)-approximate search returns a point within (1+ε) times the true nearest distance; in practice quality is reported as 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. against exact results and traded off against queries per second, memory and index-build time. Main families are tree-based partitioning (k-d trees, random-projection forests), hashing (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.), clustering-based inverted-file (IVF) indexes that probe only the partitions nearest the query, compression (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.) and proximity graphs (HNSWHNSW, abbr.: A 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., DiskANN), often combined. ANN search makes 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. over millions to billions of embeddingstext embedding, n.: A list of numbers that captures what a piece of text means, so that texts with similar meanings get similar lists. Computers use them to search, sort and group text by meaning. feasible and underlies 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. and libraries such as 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..
Raising efSearch from 64 to 256 lifted ANN recall from 0.93 to 0.99 but halved throughput.
Origin
Exact nearest neighbor search becomes impractical in high dimensions (the curse of dimensionalitycurse of dimensionality, n.: The problems that pile up when each item is described by very many measurements: even huge datasets end up thinly scattered across the possibilities, and 'near' and 'far' stop meaning much.). Approximate formulations were developed in computational geometry in the 1990s, notably by Sunil Arya, David Mount and colleagues (from 1993) and by Piotr Indyk and Rajeev Motwani (1998), who introduced locality-sensitive hashing. Quantization and graph methods from about 2011 onward made billion-scale search practical.
Usage note
Here 'ANN' should not be confused with ANN for artificial neural network. Speed claims are meaningful only at a stated recall, which is why benchmarks compare methods on recall–throughput curves.
Related
- 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.
- HNSWHNSW, abbr.: A 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.
- 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.
- 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.
- 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.
- 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.
- curse of dimensionalitycurse of dimensionality, n.: The problems that pile up when each item is described by very many measurements: even huge datasets end up thinly scattered across the possibilities, and 'near' and 'far' stop meaning much.
Sources
- Indyk, P. & Motwani, R. (1998). Approximate nearest neighbors: towards removing the curse of dimensionality. Proceedings of the 30th ACM Symposium on Theory of Computing (STOC).
- Malkov, Y. A. & Yashunin, D. A. (2016). Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs. arXiv:1603.09320. arxiv.org/abs/1603.09320v2
Mentioned in
recommender systemrecommender system, n.: Software that guesses which songs, products, posts or jobs you are most likely to want and shows those first, as when a video app lines up the next clip or a shop suggests an add-on., dense retrievaldense retrieval, n.: Finding relevant documents by turning the question and every document into lists of numbers that capture meaning, then picking the documents whose numbers are closest to the question's., Euclidean distanceEuclidean distance, n.: How far apart two points are in a straight line, as a ruler would measure it, extended from two or three dimensions to lists of numbers of any length., 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., HNSWHNSW, abbr.: A 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., inverted indexinverted index, n.: A lookup table that lists, for every word, all the documents containing it — like the index at the back of a book — so a search engine can find matches almost instantly., k-nearest neighborsk-nearest neighbors, n.: Predicting something about a new example by finding the few most similar examples already known and going with their majority answer, or their average., 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., two-tower modeltwo-tower model, n.: A design for recommendation and search in which one neural network turns users or queries into lists of numbers and another does the same for items, so good matches can be found by quick comparison., 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., generative recommendationgenerative recommendation, n.: A newer approach to recommendation that uses language-model-style AI to predict the next item a person will want, one step at a time, much as a chatbot predicts the next word., Johnson–Lindenstrauss lemmaJohnson–Lindenstrauss lemma, n.: A surprising fact about high-dimensional data: a random projection can squash a large set of points into far fewer dimensions while distorting every distance between them only slightly., 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., Matryoshka embeddingMatryoshka embedding, n.: An embedding built like a set of Russian nesting dolls: its first few numbers already give a rough summary, so you can cut it short to save space and still search reasonably well., 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., vector quantizationvector quantization, n.: Compressing data by replacing each item with the nearest entry from a small catalog of representative examples, so that only the catalog number needs to be stored or sent.