Approximate Nearest Neighbor (ANN)

Hierarchical Navigable Small World graphs build a multi-layered structure where long-range edges at higher layers enable fast coarse-grained navigation, while lower layers refine the search locally. This structure delivers logarithmic time complexity and is the dominant algorithm for high-recall, low-latency scenarios.

• Key Mechanism: Greedy routing on a proximity graph with an entry point at the top layer.
• Performance: Achieves >95% recall with sub-millisecond latency on million-scale datasets.
• Trade-off: High memory overhead due to storing all graph edges; index construction is CPU-intensive.

IVF reduces the search scope by first clustering the vector space into partitions using k-means. A query probes only the nearest nprobe centroids, drastically cutting the number of distance computations. This coarse quantization is often paired with Product Quantization for compression.

• Key Mechanism: Full-resolution vectors are assigned to the closest centroid; search is restricted to the most promising partitions.
• Performance: Excellent memory-to-speed ratio; recall is directly tunable via the nprobe parameter.
• Trade-off: Recall degrades if a relevant vector falls outside the probed partitions due to boundary effects.

Product Quantization (PQ) decomposes high-dimensional vectors into independent sub-vectors and quantizes each using a separate codebook. Scalar Quantization (SQ) converts 32-bit floats to 8-bit integers. Both techniques dramatically reduce the memory footprint, enabling billion-scale indices to reside in RAM.

• Key Mechanism: PQ compresses a 768d vector from 3KB to ~96 bytes with minimal structural loss.
• Performance: Enables exact-distance approximation without decompression via asymmetric distance computation.
• Trade-off: Aggressive compression introduces quantization error, lowering effective recall.

LSH uses randomized hash functions designed so that similar vectors collide in the same bucket with high probability. It was the foundational ANN technique for high-dimensional data before graph-based methods became dominant.

• Key Mechanism: Multiple hash tables are constructed; candidates are retrieved from buckets where the query hashes.
• Performance: Extremely fast index construction and theoretically sound guarantees for specific distance metrics like cosine and Jaccard.
• Trade-off: Requires a large number of hash tables for acceptable recall, leading to high memory usage and inferior recall-per-latency compared to HNSW.

DiskANN is a graph-based algorithm optimized for scenarios where the raw vectors are too large to fit in RAM and must reside on SSDs. It builds a Vamana graph with a small in-memory cache of navigation points, minimizing expensive disk reads during traversal.

• Key Mechanism: Greedy search on a graph stored on NVMe SSDs, using beam search to overlap I/O with computation.
• Performance: Achieves sub-10ms latency on billion-scale datasets using a single commodity machine, bypassing the need for pure in-memory clusters.
• Trade-off: Higher tail latency compared to pure in-memory HNSW due to unavoidable disk I/O.

Production vector indices are not static. The ability to insert, update, and delete vectors without a full rebuild is critical for applications with streaming data. Different algorithms handle this with varying degrees of grace.

• HNSW: Supports native insertion but requires careful concurrency control; periodic compaction is needed to reclaim deleted space.
• IVF: Insertion is straightforward by assigning to a cluster, but cluster centroids may drift over time, requiring re-training.
• Freshness Trade-off: Real-time indices often sacrifice some query throughput for immediate insert visibility.