What is approximate nearest neighbor search?
Finding the exact closest vectors to a query means measuring distance to every stored vector, which becomes hopeless as collections grow. ANN algorithms sidestep this by organizing vectors into clever index structures that can rule out most of the collection instantly, returning neighbors that are almost always the true closest ones at a tiny fraction of the cost.
The small approximation is usually invisible in practice, which is why ANN is the engine inside virtually every vector database.
Key takeaways
- ANN finds near-identical results to exact search at a fraction of the cost.
- It works by indexing vectors so most comparisons can be skipped.
- Recall versus speed is tunable through index parameters.
How it works
Common approaches include graph-based indexes like HNSW, which navigate a network of vectors toward the query's neighborhood, inverted-file indexes that search only the most promising partitions, and product quantization, which compresses vectors so more of them fit in memory. Each offers dials that trade recall against latency and memory.
Why it matters
ANN is what makes embedding-based workflows interactive at dataset scale: without it, find-similar queries over millions of images would take minutes instead of milliseconds. Understanding the recall trade-off also explains why a similarity index can occasionally miss an item an exhaustive search would find.
Frequently asked questions
How accurate is approximate nearest neighbor search?
Well-tuned indexes routinely reach 95 to 99 percent recall of the true nearest neighbors, and the setting is adjustable.
What is HNSW?
Hierarchical navigable small world graphs, the most widely used ANN index, which searches by hopping through a layered graph of vectors toward the query.
Related terms
Go deeper