Approximate Nearest Neighbor (ANN)

The fundamental premise of ANN is accepting a <1% to 5% drop in Recall@K to achieve sub-millisecond query times over billion-scale datasets. Unlike exact K-Nearest Neighbors (KNN), which performs a linear scan with O(N*D) complexity, ANN algorithms build an index that allows for sub-linear search. The trade-off is controlled by tunable parameters that let engineers dial precision up or down based on latency budgets.

Techniques like Product Quantization (PQ) and Scalar Quantization (SQ) compress high-dimensional vectors into compact codes. PQ decomposes the vector space into subspaces and clusters each independently, enabling an inverted file index (IVF-PQ) that stores only short codes. This dramatically reduces memory usage, allowing billion-scale datasets to fit in RAM. The trade-off is a slightly lower recall compared to graph-based methods, as the compression is lossy.

Algorithms like Annoy (Approximate Nearest Neighbors Oh Yeah) build a forest of random projection trees. Each tree recursively splits the vector space with random hyperplanes, creating a binary partition. At query time, the forest is traversed to collect candidates from the leaf nodes. Annoy is particularly effective for static, read-heavy datasets where index build time is less critical. It uses memory-mapped files to minimize RAM usage.

An early and theoretically elegant approach where random hash functions are designed to collide similar vectors into the same bucket with high probability. The query vector is hashed, and candidates are retrieved only from the matching bucket. While simple and parallelizable, LSH often requires a large number of hash tables to achieve competitive recall, leading to high memory usage. It has largely been superseded by graph and quantization methods for dense vectors.

A graph-based ANN algorithm that constructs a multi-layered navigable structure to achieve logarithmic scaling complexity for vector search.

• Mechanism: Builds a hierarchy of proximity graphs where long-range edges exist in top layers and short-range edges in bottom layers.
• Greedy Search: Navigates from the top layer downward, using a heuristic to prune the candidate set.
• Performance: Offers state-of-the-art speed-recall trade-offs without requiring training, making it the default index in many vector databases.

A vector compression technique that decomposes the original high-dimensional space into a Cartesian product of lower-dimensional subspaces and quantizes each independently.

• Memory Reduction: Compresses vectors by up to 16x, enabling storage of billion-scale indexes in RAM.
• Distance Computation: Uses asymmetric distance computation (ADC) to estimate similarity without decompressing the full vector.
• Trade-off: Introduces a small but controllable loss in recall in exchange for massive memory savings.

A metric measuring the cosine of the angle between two vectors, commonly used to quantify semantic similarity in normalized embedding spaces.

• Range: Returns values between -1 (opposite) and 1 (identical), with 0 indicating orthogonality.
• Normalization: When vectors are L2-normalized, cosine similarity becomes equivalent to inner product, simplifying distance calculations.
• Use Case: The dominant similarity metric for text embeddings because it ignores magnitude differences and focuses on directional alignment.

A mathematical technique used to project high-dimensional embeddings into a lower-dimensional space for visualization or compression.

• PCA: Principal Component Analysis finds orthogonal axes of maximum variance for linear projection.
• UMAP: Uniform Manifold Approximation and Projection preserves both local and global structure, often used for cluster visualization.
• Application: Enables 2D or 3D plotting of embedding spaces to debug retrieval quality and identify data clusters.

An evaluation metric measuring the proportion of relevant documents successfully retrieved within the top-K results.

• Formula: Recall@K = (Number of relevant items in top-K) / (Total number of relevant items).
• ANN Benchmarking: The primary metric for tuning ANN indexes, balancing against queries per second (QPS).
• Typical Targets: Production systems often target Recall@10 > 0.95, meaning 95% of true nearest neighbors appear in the top 10 results.