Approximate Nearest Neighbor (ANN)

ANN algorithms achieve query times that scale logarithmically or sublinearly with the dataset size, rather than the O(N) cost of brute-force exact search. This is accomplished by pruning the search space using index structures that organize vectors into navigable partitions.

• HNSW achieves O(log N) complexity through hierarchical graph traversal
• IVF reduces scope to a small fraction of clusters via inverted indexing
• LSH uses hash collisions to limit comparisons to a single bucket

Without this property, serving recommendations from billion-scale embedding catalogs in under 10ms would be computationally infeasible.

Graph-based algorithms like Hierarchical Navigable Small World (HNSW) construct proximity graphs where nodes represent vectors and edges connect near neighbors. Search proceeds via greedy traversal: starting from an entry point, the algorithm iteratively moves to the neighbor closest to the query until no closer neighbor exists.

• Long-range edges in upper layers enable logarithmic scaling by skipping across large regions of the space
• Local edges in lower layers refine the result to high precision
• No training phase required beyond graph construction, unlike clustering-based methods

HNSW consistently achieves state-of-the-art recall-speed trade-offs on high-dimensional embedding benchmarks.

Quantization techniques compress high-dimensional float32 vectors into compact codes, dramatically reducing memory footprint and enabling faster distance computations via lookup tables.

• Product Quantization (PQ) splits vectors into sub-vectors and quantizes each independently, achieving 4-8x compression
• Scalar Quantization (SQ) maps each dimension to an 8-bit integer, halving memory with minimal recall loss
• Binary quantization reduces vectors to single bits, enabling Hamming distance computation via hardware-accelerated XOR operations

These methods are critical for serving billion-scale indices within the memory constraints of a single machine.

Tree-based and clustering methods partition the vector space into disjoint or overlapping regions, restricting search to a small subset of the index.

• Inverted File Index (IVF) clusters vectors using k-means and searches only the nearest centroids to the query
• Random Projection Trees recursively split space with random hyperplanes, well-suited for low intrinsic dimensionality
• KD-Trees partition along axis-aligned splits but degrade exponentially with dimension, limiting practical use beyond ~20 dimensions

IVF combined with PQ (IVFPQ) remains the most widely deployed approach in production vector databases due to its simplicity and predictable performance.

Locality-Sensitive Hashing (LSH) uses hash functions designed so that similar vectors collide into the same bucket with high probability. Querying reduces to hashing the query vector and computing exact distances only within the collided bucket.

• Random projection LSH uses random hyperplanes; the sign of the dot product determines the hash bit
• Spherical LSH partitions the unit hypersphere for cosine similarity
• Multi-probe LSH examines multiple nearby buckets to boost recall without increasing hash table count

LSH offers theoretical guarantees on query time but typically underperforms graph-based methods on recall in high dimensions.

Every ANN algorithm operates on a recall-latency trade-off curve. Tuning hyperparameters shifts performance along this frontier without crossing it.

• ef_search in HNSW controls beam width during search: higher values increase recall at the cost of proportional latency
• nprobe in IVF determines how many clusters to search: more probes mean higher recall but more distance computations
• PQ code length trades compression ratio against reconstruction error

Production systems typically target 95-99% recall@10 with p99 latency under 10ms, selecting the algorithm and parameters that meet both constraints on the target hardware.