Approximate Nearest Neighbor (ANN) Search

These algorithms recursively partition the vector space using hierarchical tree structures. KD-Trees and Ball Trees are classic examples. They work by creating axis-aligned or hyper-spherical splits, creating a binary tree where each leaf node contains a subset of points.

• Pros: Can provide exact nearest neighbor search and is intuitive. Effective in lower-dimensional spaces.
• Cons: Suffers from the "curse of dimensionality"; performance degrades rapidly beyond ~20 dimensions as partitioning becomes less meaningful.
• Use Case: Best for exact search on lower-dimensional, structured data. Often used as a component in hybrid ANN systems.

LSH is a probabilistic technique that hashes input items so that similar items map to the same "buckets" with high probability. It uses families of hash functions that are "sensitive" to distance (e.g., Euclidean, Cosine).

• Core Mechanism: Multiple hash tables are built using different, randomized hash functions. A query is hashed to a bucket in each table, and candidates are unioned from all buckets for distance evaluation.
• Pros: Theoretically grounded, highly tunable via the number of hash tables and functions. Naturally supports sub-linear query time.
• Cons: Can require significant memory for many hash tables. Accuracy is probabilistic and highly dependent on parameter tuning.
• Example: E2LSH (Exact Euclidean LSH) is a well-known implementation.

This family constructs a graph where data points are nodes, and edges connect to their nearest neighbors. Search is performed by greedy graph traversal from an entry point to a query's vicinity. Hierarchical Navigable Small World (HNSW) graphs are the state-of-the-art.

• HNSW Mechanics: Builds a multi-layer graph. The bottom layer contains all points, and higher layers are exponentially sparser. Search starts at the top layer (fast, coarse navigation) and descends to refine.
• Pros: Extremely fast and accurate query performance. Excellent recall with low latency. Dynamic—supports incremental inserts efficiently.
• Cons: Higher memory overhead for storing the graph structure. Build time can be slower than other methods.
• Dominant Use: The default algorithm in many vector databases (e.g., Weaviate, Qdrant) and libraries like FAISS.

These algorithms reduce memory footprint and accelerate distance calculations by compressing the original vectors. Product Quantization (PQ) is the most prominent method.

• Product Quantization (PQ): Splits each high-dimensional vector into sub-vectors and quantizes each subspace independently using a small codebook. The original vector is represented by a short code of centroid IDs.
• Distance Calculation: Uses pre-computed lookup tables for distances between sub-vectors, enabling fast approximate distance computations.
• Pros: Drastically reduces memory usage (by 10x-50x). Enables holding billion-scale indexes in RAM.
• Cons: Introduces quantization error, reducing accuracy. Often combined with other methods (e.g., IVF-PQ in FAISS).
• Hybrid Example: Inverted File Index with Product Quantization (IVF-PQ) first clusters data (IVF) and then applies PQ to residuals within each cluster.

This approach uses clustering (e.g., k-means) to partition the dataset. An inverted index maps each cluster centroid to the list of vectors belonging to that cluster (a "voronoi cell").

• Search Process: For a query, find the nprobe nearest centroids. Then, perform an exhaustive search only within the vectors assigned to those selected clusters.
• Pros: Simple and effective. Significantly reduces the search space. Fast build time.
• Cons: Accuracy depends heavily on the number of clusters (nlist) and probes (nprobe). Clustering quality degrades in very high dimensions.
• Common Implementation: The IVF index in FAISS. It is frequently combined with Flat, PQ, or SQ (Scalar Quantization) for post-clustering compression.

Production ANN systems rarely use a single algorithm in isolation. They combine the strengths of multiple families to optimize the speed-accuracy-memory trade-off triangle.

• IVF + Graph (e.g., DiskANN): Uses a graph for search but stores vectors on disk, keeping only quantized vectors in RAM for guiding the search. Enables billion-scale search on a single machine.
• IVF + PQ (FAISS): The industry standard for large-scale in-memory search. Clustering (IVF) reduces scope, and Product Quantization compresses the vectors within each cell.
• HNSW + PQ: A graph (HNSW) built on top of quantized vectors, reducing memory overhead while maintaining high recall.
• Scalar Quantization (SQ): A simpler quantization than PQ, converting 32-bit floats to 8-bit integers uniformly. Often used with IVF for a good balance of speed and accuracy.
• Selection Principle: The choice depends on dataset size, dimensionality, accuracy requirements (recall@K), and hardware constraints (RAM vs. SSD).

A state-of-the-art, graph-based algorithm for approximate nearest neighbor search. HNSW constructs a hierarchical graph where long-range links enable fast, greedy traversal from coarse to fine layers, providing a strong trade-off between recall, speed, and memory efficiency. It is widely implemented in libraries like FAISS and is a popular choice for production vector databases due to its performance characteristics and relatively simple tuning parameters.

The predominant metric used to measure similarity between vector embeddings in ANN search. It calculates the cosine of the angle between two non-zero vectors in an inner product space, effectively measuring their orientation rather than magnitude. This makes it ideal for comparing semantic embeddings generated by models like sentence transformers, where the direction of the vector encodes meaning. The search objective in most ANN systems is to find vectors with the highest cosine similarity to a query vector.

A family of compression techniques that reduce the precision of numerical values (e.g., from 32-bit floating-point to 8-bit integers) to decrease the memory footprint and computational cost of vector search. Product Quantization (PQ) is a specific, powerful method that decomposes the high-dimensional space into subspaces and quantizes each separately, enabling efficient distance calculations using lookup tables. Quantization is critical for scaling ANN search to billions of vectors in memory-constrained environments.

The primary accuracy metric for evaluating ANN search algorithms. It measures the proportion of true nearest neighbors (from an exact, brute-force search) that are found within the top K results returned by the approximate algorithm. For example, a Recall @ 10 of 0.95 means 95% of the true top-10 neighbors were retrieved. Engineers tune ANN parameters (like the number of probes in IVF or the efSearch in HNSW) to achieve the optimal balance between this recall and query latency for their specific application.