Approximate Nearest Neighbor (ANN) Search

The fundamental premise of ANN search is trading a small, quantifiable amount of recall for orders-of-magnitude improvements in query latency. Unlike exact brute-force search, which scales linearly with dataset size, ANN algorithms operate in sub-linear time by restricting the search space. The recall@K metric quantifies this tradeoff, measuring the fraction of true nearest neighbors retrieved.

• A recall of 0.99 means 99% of the true top results are found, often with a 100x speedup.
• The acceptable recall level is application-specific; semantic search often tolerates 0.95 recall, while critical retrieval demands 0.99+.

ANN indices must balance the fidelity of stored vectors against available hardware resources. Vector compression techniques like Product Quantization (PQ) and scalar quantization reduce memory footprints by encoding high-dimensional vectors into compact codes, enabling billion-scale datasets to reside in RAM. This compression introduces quantization error, a distortion that directly impacts search precision.

• Raw float32 vectors consume 4 bytes per dimension; PQ can compress this to 0.5 bytes per dimension.
• DiskANN pushes this further by storing the graph on SSD, minimizing RAM usage for trillion-scale indexes.

There is a distinct operational tradeoff between the computational cost of constructing an index and its ultimate query performance. Graph-based algorithms like HNSW achieve exceptional query speed but require significant upfront build time to construct a high-quality proximity graph with optimal graph degree and connectivity. Conversely, clustering-based methods like IVF build faster but may yield lower recall for a given query time.

• Build time is critical for dynamic datasets requiring frequent re-indexing.
• Global optimizations during a slow build often enable millisecond-level queries.

Combining vector similarity with structured metadata filters introduces significant complexity. Pre-filtering applies constraints before ANN search, which can break graph connectivity and cause severe recall degradation if the filter is too restrictive. Post-filtering retrieves a larger candidate set and then applies filters, guaranteeing correct results but potentially returning zero items if the ANN index is unaware of the filter.

• Hybrid strategies merge both approaches to balance recall and correctness.
• This remains an active area of research for vector databases supporting rich metadata queries.

ANN algorithms are optimized for specific distance metrics, and the choice of metric fundamentally alters the geometry of the search space. Euclidean distance is sensitive to vector magnitude, while cosine similarity measures only angular difference. Maximum Inner Product Search (MIPS) is critical for attention mechanisms but cannot be directly converted to Euclidean distance without violating metric space properties.

• Algorithms like ScaNN are specifically designed to optimize the recall-speed tradeoff for MIPS.
• Using the wrong metric for an index will produce semantically meaningless results.

A leading graph-based ANN algorithm that constructs a multi-layered proximity graph. Search begins in the sparsest top layer, taking long-range hops, and descends to denser lower layers for refinement. This structure provides logarithmic scaling complexity, offering an excellent trade-off between high recall and fast query times without requiring a separate training phase like clustering methods.

A vector compression technique that decomposes high-dimensional vectors into smaller subvectors. Each subvector is independently quantized using a distinct codebook learned via k-means clustering. This dramatically reduces the memory footprint, allowing billion-scale datasets to reside in RAM. Distance calculations are performed using efficient lookup tables, trading a small amount of precision for massive storage savings.

A clustering-based ANN structure that partitions the vector space into Voronoi cells using a coarse quantizer. A query vector is first assigned to its nearest centroid(s), and the exhaustive search is restricted to only those partitions. This significantly reduces the number of distance computations, making it a foundational component in composite indexes like IVFPQ.

The standard evaluation metric for ANN search, measuring the fraction of true nearest neighbors found within the top K retrieved results. It quantifies the accuracy loss introduced by approximation. For example, Recall@10 of 0.95 means 95% of the true 10 nearest neighbors were retrieved. This metric is the primary variable traded against query speed and memory usage when tuning an index.

A two-stage retrieval architecture that mitigates the accuracy loss from vector compression. A fast ANN index using compressed vectors retrie a large candidate set. A second, more expensive computation then re-scores these candidates using full-precision vectors or a cross-encoder model. This combines the speed of approximate search with the accuracy of exact distance calculations on a much smaller subset.