Approximate Nearest Neighbor Search

Approximate nearest neighbor (ANN) search is the problem of finding points in a dataset that are close — but not necessarily the absolute closest — to a query point under some distance metric, typically Euclidean distance or cosine similarity on dense vector embeddings. It is the workhorse behind Semantic Search: Finding Content by Meaning Instead of Keywords, recommendation systems, deduplication, and retrieval for RAG (Retrieval-Augmented Generation): How LLMs Access External Knowledge. Exact k-nearest-neighbor search scales poorly because of the curse of dimensionality: as the number of dimensions grows, pairwise distances concentrate into a narrow band, and tree-based indexes such as the KD-tree or ball tree degrade toward a linear scan. Useful embedding spaces today commonly have 384 to 4096 dimensions, where exact search across millions of vectors is prohibitively slow. ANN methods trade a small loss of recall — some true neighbors are missed — for orders-of-magnitude gains in latency and throughput. Four algorithm families dominate. Tree-based partitioning (KD-tree, ball tree, random projection trees) works well in low dimensions and underlies the Annoy library. Locality-sensitive hashing (LSH) uses hash families that map nearby points to the same bucket with high probability, giving sublinear query time with provable guarantees. Graph-based methods, most notably HNSW (Hierarchical Navigable Small World, Malkov and Yashunin, 2016), build a multi-layer proximity graph and greedily descend it from coarse to fine granularity, achieving logarithmic search complexity with high recall. Product quantization (PQ), introduced by Jégou and colleagues in 2011, splits vectors into subspaces and encodes each with a small codebook, compressing memory by roughly 90–97% while supporting approximate distance computation in the compressed domain. ANN performance is characterized by a recall–latency–memory trade-off, tuned per workload. Graph indexes like HNSW give the best recall at low latency but use more memory; PQ shrinks memory at the cost of some precision; LSH offers theoretical bounds; tree methods favor static, memory-mapped datasets. Production libraries combine techniques: FAISS (Meta) offers GPU-accelerated PQ, IVF, and HNSW variants; hnswlib provides a focused, high-recall HNSW implementation; Annoy targets read-heavy offline workloads; ScaNN (Google) pairs partitioning with anisotropic quantization for accelerator hardware. Public benchmarks such as ann-benchmarks plot recall against queries per second, letting practitioners pick the operating point that fits their accuracy budget.