Approximate Nearest Neighbor (ANN)

Approximate Nearest Neighbor (ANN) search is the class of algorithms that powers fast similarity lookups in a vector database. Exact nearest-neighbour search compares a query against every stored vector, which becomes prohibitively slow at millions or billions of vectors. ANN algorithms instead search only a carefully chosen subset of the space, accepting a small loss in accuracy (measured as recall) in exchange for dramatic latency reductions.

Common ANN approaches

The two dominant families are graph-based and cluster-based indexes. HNSW builds a multi-layer navigable graph and greedily walks it from a sparse top layer down to the dense bottom layer, delivering high recall and fast queries at the cost of more memory and longer build times. IVF (Inverted File) partitions vectors into clusters with k-means and searches only the clusters nearest the query, often combined with Product Quantization (PQ) to compress vectors and shrink memory.

The recall/latency trade-off

Every ANN index exposes tuning parameters that move you along a curve between speed and recall. Searching more graph neighbours or more clusters raises recall but costs latency and compute. For a self-hosted retrieval stack, you tune these to fit your hardware budget rather than chasing perfect accuracy you do not need.

ANN is what makes private, on-premise semantic search feasible on a single workstation. It lets a self-custody compute setup query a large corpus of embeddings in milliseconds without shipping data to a third party.