Approximate Nearest Neighbor Search (ANN)

ANN algorithms replace exhaustive, brute-force distance calculations with probabilistic indexing structures. Instead of comparing a query vector against every vector in the database (an O(N) problem), ANN restricts the search to a small, highly probable subset of candidates. This introduces a controlled recall penalty—typically less than 1%—in exchange for a 100x to 1000x speedup. The core mechanism relies on the geometric properties of high-dimensional spaces, where vectors cluster naturally, allowing the algorithm to prune vast irrelevant regions of the space without inspection.

The Hierarchical Navigable Small World (HNSW) algorithm constructs a multi-layered graph structure. The top layers contain long-range "highway" edges that enable rapid traversal across the vector space, while bottom layers hold short-range edges for fine-grained local search. During a query, the algorithm performs a greedy beam search, starting at a fixed entry point on the top layer and descending, always moving to the neighbor closest to the query vector. This navigable structure provides logarithmic search complexity and is the default index in vector databases like Weaviate and Milvus.

This two-stage approach combines Inverted File (IVF) partitioning with Product Quantization (PQ). First, the vector space is partitioned into Voronoi cells using k-means clustering; a query only searches the nearest cells. Second, vectors within those cells are compressed via PQ, which decomposes high-dimensional vectors into smaller sub-vectors and quantizes each independently. This drastically reduces memory footprint and enables fast distance approximation using pre-computed lookup tables. IVF-PQ is ideal for memory-constrained environments where RAM is the primary cost driver.

Developed by Spotify, Approximate Nearest Neighbors Oh Yeah (ANNOY) builds a forest of random projection trees. Each tree recursively splits the vector space with random hyperplanes, creating binary partitions. At query time, the algorithm traverses each tree to the leaf containing the query point and collects all vectors from those leaves as candidates. The forest structure allows the index to be memory-mapped from disk, enabling multiple processes to share the same static index without loading duplicates into RAM. This makes ANNOY particularly suited for read-heavy, multi-tenant deployments.

LSH uses a family of hash functions with a special property: vectors that are close in the original space have a high probability of colliding in the same hash bucket, while distant vectors do not. A query vector is hashed, and only vectors in the same bucket are considered candidates. The process is repeated with multiple hash tables to boost recall. LSH offers strong theoretical guarantees on query time and is deterministic in its index construction, but it typically requires more memory than graph-based methods to achieve competitive recall rates.

When vector collections exceed available RAM, DiskANN and similar algorithms provide a solution. DiskANN builds a graph-based index like HNSW but optimizes the layout of vectors on SSD storage to minimize random reads. It uses a compressed representation of the graph in memory alongside a small, cached set of full-precision vectors. During search, the algorithm intelligently prefetches candidate vectors from disk, overlapping I/O latency with computation. This enables billion-scale similarity search on a single commodity machine without requiring an in-memory index.