Approximate Nearest Neighbor (ANN)

ANN algorithms exchange a small, controllable amount of recall (the fraction of true nearest neighbors returned) for a massive reduction in query latency. Unlike brute-force k-NN search, which scales linearly with the dataset size O(N), ANN methods achieve sub-linear or logarithmic complexity. This is not a bug but a deliberate engineering choice: in high-dimensional spaces, the concept of a 'nearest' neighbor is often fuzzy, making a 99% recall with 1ms latency vastly more valuable than 100% recall with 100ms latency for user-facing personalization.

Hierarchical Navigable Small World (HNSW) is the dominant graph-based ANN algorithm. It constructs a multi-layered proximity graph where sparse upper layers contain long-range links for rapid coarse navigation, and dense lower layers contain short-range links for fine-grained local search. A query traverses from the top layer downwards, greedily moving to the nearest neighbor at each level. This structure provides logarithmic search complexity, excellent recall, and supports incremental insertion without full index rebuilds, making it ideal for dynamic retail catalogs.

To fit billion-scale embedding indices in memory, ANN systems employ compression techniques. Product Quantization (PQ) decomposes a high-dimensional vector into smaller sub-vectors and quantizes each independently using a learned codebook, compressing a 1024-dim float32 vector into a few bytes. Scalar Quantization (SQ) converts 32-bit floats to 8-bit integers. These compressed representations are used for rapid distance approximation during the candidate scanning phase, dramatically reducing memory bandwidth requirements while preserving semantic similarity.

The Inverted File (IVF) index partitions the vector space into clusters using k-means. At query time, instead of comparing against every vector, the algorithm probes only the closest nprobe clusters. This coarse quantization acts as a pre-filter, drastically reducing the candidate set. IVF is often combined with PQ (forming IVFPQ) to achieve both coarse spatial partitioning and fine-grained vector compression, providing a highly tunable knob between speed and accuracy via the nprobe parameter.

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 applying multiple hash tables, the algorithm retrieves candidates by hashing the query vector and fetching all vectors that share a bucket. While historically foundational, LSH often requires more memory and provides lower recall than modern graph-based methods for high-dimensional embeddings, though it remains relevant for specific distance metrics like Jaccard similarity.

Real-world retail personalization requires combining vector similarity with structured filters (e.g., 'in-stock', 'category=shoes', 'price < $100'). Naively applying post-filters breaks recall guarantees. Advanced ANN engines support pre-filtering (restricting the search space) or filter-aware graph traversal that skips nodes violating constraints. This hybrid capability is critical for serving a query like 'find items visually similar to this dress, but only in size M and on sale,' ensuring both semantic relevance and business rule compliance.