Approximate Nearest Neighbor (ANN)

The defining characteristic of ANN is the deliberate sacrifice of perfect accuracy for sub-linear query times. Unlike exact k-NN, which performs an exhaustive O(N) comparison, ANN algorithms use index structures to prune the search space. The trade-off is governed by a tunable parameter (often epsilon or efSearch) that controls the recall rate—the fraction of true nearest neighbors returned. A typical production setting targets 95-99% recall, achieving query latencies measured in milliseconds rather than seconds, which is essential for real-time personalization engines serving cold-start users.

The Hierarchical Navigable Small World (HNSW) algorithm is a leading graph-based ANN method. It constructs a multi-layered graph where each layer is a proximity graph. The top layers contain long-range "highway" edges for rapid coarse navigation, while the bottom layer contains short-range edges for fine-grained search. A query traverses from the top layer downward, greedily moving to the nearest neighbor at each step. This navigable small-world property ensures a logarithmic number of hops, making it exceptionally fast and the default choice in vector databases like Weaviate and Milvus.

The Inverted File (IVF) index partitions the vector space into Voronoi cells using k-means clustering. During a query, the algorithm probes only the cell(s) closest to the query vector, drastically reducing the number of distance computations. The nprobe parameter controls how many cells to search, directly tuning the accuracy-speed trade-off. IVF is often combined with Product Quantization (PQ) to compress the vectors within each cell, enabling massive datasets to fit in RAM. This combination, IVF-PQ, is a foundational technique in the FAISS library.

Locality-Sensitive Hashing (LSH) uses a family of hash functions designed so that similar vectors have a high probability of colliding in the same hash bucket. By using multiple hash tables, the algorithm ensures that a query's true neighbors are likely to be found in at least one matching bucket. LSH offers theoretical guarantees on recall probability and is particularly effective for high-dimensional sparse data. However, for dense embeddings, graph-based methods often outperform it in practice due to lower memory overhead and faster empirical query times.

Product Quantization (PQ) is a lossy compression technique critical for scaling ANN to billion-scale datasets. It decomposes a high-dimensional vector into sub-vectors and quantizes each independently using a separate codebook. The distance between a query and a database vector is then approximated by summing pre-computed look-up table values. This reduces memory consumption from 4 bytes per float to a few bits per component, allowing the entire index to reside in RAM. PQ is the engine behind the compactness of IVF-PQ and is essential for cold-start item retrieval from massive catalogs.

ANN is the operational backbone for content-based cold start solutions. When a new user provides an initial query or clicks a single item, that signal is encoded into a dense embedding. An ANN index then retrieves the top-k nearest item embeddings from the catalog in real-time. This bypasses the need for collaborative filtering history. The speed of ANN enables session-based recommendation, where the system can re-rank results after every user action within a single anonymous session, progressively refining the understanding of intent without a persistent profile.

The dense, low-dimensional numerical representation of data (users, items, text) that encodes semantic meaning. ANN algorithms operate directly on these vectors.

• Dimensionality: Typically ranges from 50 to 4096 dimensions
• Semantic Compression: Similar items are placed closer together in the vector space
• Cold Start Role: Pre-trained embeddings from content-based models provide the initial vector for a new item, enabling immediate ANN retrieval without interaction history

A state-of-the-art graph-based ANN algorithm that constructs a multi-layered navigable structure. It provides logarithmic scaling for search complexity and is the default index in many vector databases.

• Mechanism: Builds a hierarchy of proximity graphs, searching from the top layer down
• Performance: Achieves sub-millisecond query latency on billion-scale datasets
• Trade-off: Higher memory consumption compared to quantization-based methods due to storing the full graph structure

A classical ANN technique that hashes input vectors so that similar items map to the same buckets with high probability. It provides a probabilistic guarantee of sub-linear search time.

• Hash Function Design: Uses random hyperplane projections or p-stable distributions
• Amplification: Employs multiple hash tables to boost recall by combining results
• Use Case: Effective for high-dimensional sparse data and cosine similarity, often used as a baseline for cold-start retrieval benchmarks

A compression technique that decomposes the high-dimensional vector space into lower-dimensional subspaces and quantizes each independently. It dramatically reduces the memory footprint of an index.

• Codebook Learning: Clusters each subspace using k-means to create a discrete codebook
• Distance Computation: Uses asymmetric distance computation for fast approximate scoring
• Benefit: Enables in-memory indexing of billion-scale vector collections on commodity hardware, critical for large retail catalogs

The fundamental distance metric used in most ANN retrieval systems, measuring the cosine of the angle between two non-zero vectors. It is invariant to vector magnitude, focusing purely on directional alignment.

• Range: Returns a value between -1 (opposite) and 1 (identical direction)
• Normalization: Often combined with L2 normalization to convert it into an inner product search
• Cold Start Application: Used to match a new user's sparse preference vector against pre-computed item embeddings to find the nearest neighbors

The primary evaluation metric for ANN algorithms, measuring the fraction of true nearest neighbors found in the top-k retrieved results. It quantifies the accuracy loss introduced by approximation.

• Typical Targets: Production systems often target 95-99% Recall@10
• Trade-off: Higher recall requires more exhaustive search, increasing latency
• Tuning: System designers balance the recall-latency curve by adjusting index parameters like ef_search in HNSW or the number of probes in IVF