Approximate Nearest Neighbor (ANN)

Approximate Nearest Neighbor (ANN) is a family of algorithms that find the approximately closest vectors to a query vector in sublinear time, trading small amounts of recall for orders-of-magnitude speedups over exact search. Exact nearest-neighbor search over N vectors of D dimensions costs O(N × D) per query — tractable for a few thousand vectors but infeasible at the 10M-to-1B scale where modern vector databases operate. ANN algorithms achieve sub-millisecond query times at those scales by building an index structure (graph, tree, hash, or quantisation-based) that lets queries navigate to a small high-quality candidate set without comparing against every vector.

The 2026 ANN landscape is dominated by three index families. **HNSW (Hierarchical Navigable Small World)** — graph-based, logarithmic search, excellent recall-speed trade-off, memory-hungry — powers most managed vector databases at small to medium scale. **IVF (Inverted File Index)** and **IVF-PQ (with Product Quantisation)** — partition-based, disk-friendly, preferred at very large scale where HNSW's memory footprint becomes prohibitive — common in FAISS, Milvus, Vespa. **SCANN** (Google Research) and **DiskANN** (Microsoft Research) compete at the multi-billion-vector frontier with specialised trade-offs. GPU-accelerated ANN (NVIDIA RAPIDS cuVS, FAISS GPU) is a real option for latency-critical workloads.

For APAC mid-market teams, the practical guidance is **HNSW as default up to roughly 100M vectors, IVF-PQ beyond**. Managed vector databases hide the choice behind sensible defaults, but the team should understand what's happening: HNSW is fast and high-recall but holds the whole graph in memory; IVF-PQ shrinks memory via quantisation at the cost of some recall. Measure recall@k on your actual workload — not published benchmarks — because recall degrades with dimensionality, corpus diversity, and query distribution in ways generic benchmarks obscure.

The non-obvious failure mode is **tuning only for speed, ignoring recall**. Vector DB dashboards surface queries-per-second prominently and recall@k obscurely. Teams raise concurrent QPS by lowering efSearch or nprobe, not noticing that recall@10 quietly dropped from 95% to 78%, and then puzzle over why retrieval quality degraded after a "performance optimisation". Published benchmarks often report recall at near-optimal parameters; production tuning often lands at aggressive speed settings unless someone is explicitly watching the recall metric. Instrument both; trade them deliberately.