Exact nearest neighbor search in high dimensions is per query (brute-force scan). For millions of vectors, this is too slow. Approximate methods trade a small accuracy loss for massive speedups.
Main families:
1. Tree-based
- KD-trees — partition space by splitting along coordinate axes. Work well up to ~20 dimensions, degrade in high- (Curse of Dimensionality)
2. Hashing-based (LSH)
- Hash vectors so that similar vectors collide with high probability
- Multiple hash tables boost recall
- Sub-linear query time, but high memory
3. Graph-based (HNSW)
- Build a navigable small-world graph where nearby vectors are linked
- Greedy traversal at query time: start at entry point, greedily follow edges toward query
- State-of-the-art recall/speed tradeoff — used in most production systems
4. Quantization-based (IVF + PQ)
- Inverted File Index (IVF): cluster vectors, only search nearby clusters at query time
- Product Quantization (PQ): compress vectors into short codes for fast distance approximation
- FAISS (Meta) combines IVF + PQ for billion-scale search
Where this is essential:
- RAG (Retrieval-Augmented Generation) — retrieve relevant documents by embedding similarity
- Semantic search — find similar embeddings over large corpora
- Recommendation systems — item retrieval from embedding spaces
- Deduplication — find near-duplicate training examples at scale
- kNN classifiers at scale — K-Nearest Neighbors on large datasets
Tools: FAISS, ScaNN, Annoy, Pinecone, Weaviate, Milvus.
See also: Embeddings, Norms and Distance Metrics, Hash Tables