Approximate Nearest Neighbors (ANN)

The defining characteristic of ANN algorithms is the explicit sacrifice of perfect recall for sub-linear query times. Instead of an O(N) exact search, ANN algorithms achieve O(log N) or O(1) complexity by probabilistically skipping large regions of the vector space. Recall@K is the standard metric, measuring the fraction of true nearest neighbors returned. A well-tuned ANN index typically achieves 95-99% recall while being 100x to 1000x faster than brute-force. This trade-off is controlled by parameters like ef_search in HNSW or nprobe in IVF-based indexes, allowing operators to dial precision up or down based on latency budgets.

Modern state-of-the-art ANN algorithms like Hierarchical Navigable Small World (HNSW) construct multi-layered proximity graphs where nodes represent vectors and edges connect near neighbors. Search navigates from long-range edges in sparse upper layers down to dense local neighborhoods in lower layers, analogous to skip lists in geometric space. Key properties:

• Logarithmic scaling: Search complexity grows as O(log N) with dataset size
• No training phase: Graphs are built incrementally with insert-time linking
• Memory overhead: Requires storing both vectors and graph edges, typically 1.5-2x the raw vector footprint
• Deterministic inserts: Same data always produces the same graph structure

To reduce memory footprint and accelerate distance computations, many ANN systems employ vector quantization. Product Quantization (PQ) decomposes high-dimensional vectors into smaller sub-vectors and quantizes each independently, enabling compressed storage and fast approximate distance lookups via precomputed distance tables. Scalar Quantization (SQ) converts 32-bit floats to 8-bit integers, reducing memory by 4x with minimal recall loss. Inverted File indexes with PQ compression can store billion-scale datasets in main memory while maintaining sub-10ms query latency.

Space-partitioning methods like Inverted File (IVF) and k-means trees divide the vector space into Voronoi cells during training. At query time, only the most promising partitions are searched. Techniques include:

• IVFADC: Combines inverted file indexing with asymmetric distance computation for compressed vectors
• SCANN: Google's approach using anisotropic vector quantization with a two-stage scoring pipeline
• DiskANN: Microsoft's SSD-resident index using Vamana graphs with compressed vectors, enabling search over datasets too large for RAM Partitioning strategies are critical for scaling beyond memory limits while maintaining low latency.

One of the earliest ANN families, LSH uses hash functions designed so that similar vectors collide in the same bucket with high probability. By using multiple hash tables, recall improves at the cost of increased memory. While largely superseded by graph-based methods for high-recall applications, LSH remains relevant for:

• Streaming and dynamic datasets where index rebuilds are expensive
• Theoretical guarantees: LSH provides provable sub-linear query time bounds
• Specialized similarity measures: LSH families exist for cosine, Jaccard, and Hamming distances Modern systems like FALCONN implement multi-probe LSH that checks multiple nearby buckets per hash table.

Spatial tree structures like KD-trees, Ball trees, and Annoy (Approximate Nearest Neighbors Oh Yeah) recursively partition space using axis-aligned or spherical splits. Annoy, developed at Spotify, builds a forest of random projection trees where each tree independently partitions the space. At query time, all trees are traversed simultaneously and results are merged via a priority queue. Key characteristics:

• Static indexes: Built once and memory-mapped for read-only serving
• Tunable precision: More trees increase recall at linear memory cost
• Disk-friendly: Memory-mapped files enable serving indexes larger than RAM Tree methods excel when build time and disk residency are prioritized over maximum recall.

A graph-based ANN algorithm that constructs a multi-layered proximity graph to achieve logarithmic search complexity. Upper layers contain long-range edges for coarse navigation, while lower layers refine the search locally.

• Construction: Inserts nodes probabilistically into layers, building a navigable small-world graph
• Search: Greedy traversal from top layer to bottom, maintaining a dynamic candidate list
• Performance: Achieves sub-millisecond query times on billion-scale datasets with high recall
• Trade-off: Higher memory footprint due to storing multiple graph layers

A partition-based ANN method that clusters the vector space into Voronoi cells using k-means, then searches only the most relevant partitions.

• Training: Clusters vectors into centroids, assigning each vector to its nearest centroid
• Querying: Identifies the nprobe closest centroids and searches only those partitions
• Compression: Often combined with Product Quantization (PQ) to compress vectors in each cell
• Scalability: Excellent for billion-scale datasets with moderate memory requirements

A vector compression technique that decomposes high-dimensional vectors into smaller sub-vectors and quantizes each independently, dramatically reducing memory footprint.

• Mechanism: Splits a D-dimensional vector into M sub-vectors, each quantized to a codebook
• Distance Computation: Uses lookup tables for asymmetric distance computation between query and codes
• Memory Savings: Compresses 1024-dim float32 vectors from 4KB to as little as 64 bytes
• Application: Often paired with IVF for IVF-PQ, the backbone of FAISS billion-scale search

A probabilistic ANN method that hashes similar vectors into the same buckets with high probability, enabling sub-linear search via hash table lookups.

• Principle: Uses random projection hyperplanes to generate hash bits; similar vectors share more bits
• Querying: Hashes the query vector and retrieves candidates from matching buckets
• Strengths: Simple to implement, theoretically grounded, works with many distance metrics
• Limitations: Requires many hash tables for high recall, less competitive with graph-based methods on modern benchmarks

A disk-resident ANN framework designed to store the index on SSD while maintaining low-latency queries, enabling billion-scale search on a single commodity machine.

• Architecture: Builds a graph-based index with Vamana algorithm, optimized for minimal disk I/O
• Caching: Caches frequently accessed graph nodes in RAM, fetching the rest from SSD on demand
• Cost Efficiency: Eliminates the need for fully in-memory indexes on expensive high-RAM instances
• Adoption: Underpins Microsoft's Bing search and Azure Cognitive Search vector capabilities

Google's vector similarity search library that introduces anisotropic vector quantization to optimize for the inner product distance metric commonly used in maximum inner product search (MIPS).

• Innovation: Scores vectors based on their quantization error parallel to the original vector direction, preserving inner product fidelity
• Performance: Achieves superior recall-speed trade-offs compared to generic ANN libraries on MIPS tasks
• Integration: Powers vector search in Google products and Vertex AI Matching Engine
• Design: Purpose-built for the asymmetric nature of query-document inner product scoring