Approximate Nearest Neighbor (ANN)

The defining characteristic of all ANN algorithms is the explicit sacrifice of perfect accuracy for sub-linear query time. Unlike exact k-NN, which performs a brute-force O(N*D) comparison, ANN algorithms use index structures to prune the search space. This trade-off is governed by a recall@k metric, where a recall of 0.95 means 95% of the true nearest neighbors are returned. Tuning this parameter allows engineers to balance precision against latency and memory consumption.

The Hierarchical Navigable Small World (HNSW) algorithm is the dominant graph-based approach. It builds a multi-layered graph where long-range edges on sparse top layers enable fast coarse navigation, and short-range edges on dense bottom layers ensure high recall. Key properties include:

• Logarithmic complexity: Query time scales as O(log N).
• Incremental insertions: Supports adding vectors without a full index rebuild.
• High memory overhead: Stores the full graph structure, making it memory-intensive for large datasets.

IVF-based methods, commonly paired with Product Quantization (PQ), partition the vector space into Voronoi cells using k-means clustering. A query only searches the nearest nprobe cells. This approach excels at:

• Memory efficiency: PQ compresses vectors by decomposing them into sub-vectors and quantizing each independently.
• Disk-based storage: The inverted index structure maps naturally to on-disk storage, enabling billion-scale search on a single machine.
• Training dependency: Requires a representative sample of data to train the clustering and quantization codebooks before indexing.

LSH is a family of methods that use random projection hash functions to bucket vectors such that similar items collide with high probability. A query is hashed and only compared against vectors in the same bucket. Key characteristics:

• Theoretical guarantees: Provides provable bounds on query time and accuracy.
• Simplicity: Easy to implement and parallelize.
• Lower recall efficiency: Typically requires more memory and computation than graph-based methods to achieve the same recall, leading to its gradual replacement by HNSW in many production systems.

Spotify's ANNOY (Approximate Nearest Neighbors Oh Yeah) uses an ensemble of random projection trees. Each tree recursively splits the space with random hyperplanes, creating binary partitions. At query time, the forest is traversed to collect candidates from the leaf nodes. Its defining traits are:

• Static index: The forest is built once and cannot be modified without a full rebuild, making it ideal for read-heavy, immutable datasets.
• Memory-mapped files: Indexes are stored as files that can be shared across processes via memory mapping, enabling zero-copy serving.

To manage the memory footprint of high-dimensional vectors, ANN systems employ lossy compression. The three primary methods are:

• Product Quantization (PQ): Splits a vector into sub-vectors and quantizes each using a distinct codebook.
• Scalar Quantization (SQ): Converts 32-bit floats to 8-bit or 4-bit integers.
• Binary Embeddings: Reduces vectors to compact binary codes, where distance is computed via Hamming distance, enabling extremely fast CPU-based search.

A leading graph-based ANN algorithm that builds a multi-layered proximity graph. Lower layers contain all data points with long-range connections for fast traversal, while upper layers have fewer points with short-range links. Search begins at the top layer and descends greedily, achieving logarithmic complexity. HNSW offers an excellent trade-off between recall and queries per second, making it the default index in vector databases like Weaviate and Milvus.

A lossy compression technique that decomposes high-dimensional vectors into smaller sub-vectors and quantizes each independently using a codebook of centroids. This dramatically reduces the memory footprint of an index—a 128-dimensional float32 vector can be compressed to just 64 bytes. During search, distances are approximated using pre-computed lookup tables, trading a small accuracy loss for massive memory savings. Essential for billion-scale datasets that cannot fit in RAM.

A family of hashing functions where similar vectors collide into the same bucket with high probability. Unlike cryptographic hashes, LSH deliberately maximizes collisions for nearby points. The index is built by applying multiple hash tables; at query time, only vectors sharing buckets with the query are examined. While largely superseded by graph-based methods for dense embeddings, LSH remains relevant for sparse high-dimensional data and specific similarity measures like Jaccard and Hamming distance.

A partitioning strategy that clusters the dataset into Voronoi cells using k-means. At query time, only the nearest nprobe cells are searched exhaustively, reducing the search scope from the entire dataset to a small fraction. IVF is often combined with PQ (IVF-PQ) to achieve both search space reduction and memory compression. The trade-off is controlled by the number of probes: more probes increase recall at the cost of latency.

A graph-based ANN algorithm designed for SSD-resident indexes that are too large for RAM. DiskANN builds a Vamana graph with a small memory footprint and uses careful data layout to minimize random disk reads during search. It caches frequently accessed nodes in memory and overlaps I/O with computation, achieving sub-millisecond latency on billion-point datasets using commodity SSDs. Developed by Microsoft Research and used in Azure Cognitive Search.