What is Approximate Nearest Neighbor Search?
Also called ANN search, ANN.
Approximate nearest neighbor search is a family of algorithms that find vectors close to a query vector without guaranteeing that the very closest ones are returned. By tolerating a small chance of missing a true neighbor, these methods answer queries over millions of vectors in milliseconds instead of comparing the query against every stored record.
Exact nearest neighbor search compares a query against every vector in a collection, which is accurate but scales linearly with collection size. Once a collection reaches millions of items, that brute force scan becomes too slow for interactive use. Approximate methods build a data structure ahead of time that lets a query visit only a small fraction of the collection while still landing on most of the genuinely closest vectors.
The accuracy of an approximate search is measured as recall against an exact baseline, usually expressed as the fraction of the true top results that the approximate method also returned. Systems typically target recall in the high nineties. Every approximate algorithm exposes tuning parameters that trade recall against speed and memory, so the same index can be configured for a fast, slightly lossy search or a slower, more faithful one.
Common approaches include graph based navigation, in which the search walks a network of vector to vector links toward the query; inverted file partitioning, which clusters vectors and searches only the nearest clusters; and quantization, which compresses vectors into compact codes that are cheap to compare. Production systems often combine partitioning with quantization to keep large collections inside available memory.
Because the result set is probabilistic, an approximate search can behave differently after an index rebuild even when the underlying data has not changed. Teams that need reproducible evaluation usually pin index parameters and record them alongside retrieval metrics, and some run a periodic exact search on a sample to confirm that recall has not drifted downward as the collection grows.
Key points
- Trades a small accuracy loss for very large speed gains
- Recall against exact search is the standard quality measure
- Tuning parameters shift the speed, memory, and recall balance
- Underpins search in most vector databases
- Results can vary slightly between index builds
In practice
A support knowledge base holds four million passage vectors. An exact search would compare a question against all four million on every request, taking seconds. With an approximate index, the query touches roughly a few thousand candidates, returns in under twenty milliseconds, and includes about ninety-eight of every hundred passages that an exact search would have found. The two missing passages are almost always low-ranked ones the answer never needed.