Approximate Nearest Neighbor (ANN) Search

These methods construct a graph where nodes are data points and edges connect to nearest neighbors, enabling fast traversal.

• Hierarchical Navigable Small World (HNSW) is the dominant modern algorithm, building a multi-layered graph. Search starts at a coarse top layer and navigates greedily to the nearest neighbors, refining through layers.
• NSW (Navigable Small World) is the single-layer predecessor to HNSW.
• Pros: State-of-the-art query speed and recall, especially for high-dimensional data. Very low latency.
• Cons: High memory footprint to store the graph. Index construction can be slower than other methods.

These techniques reduce memory usage and accelerate distance calculations by compressing vectors into compact codes.

• Product Quantization (PQ) splits the high-dimensional vector into subvectors and quantizes each sub-space into a small set of centroids. A vector is represented by a short code of centroid IDs.
• Scalar Quantization reduces the precision of each vector component (e.g., from 32-bit floats to 8-bit integers).
• Pros: Drastically reduces memory footprint (often by 10x-30x). Enables holding massive billion-scale datasets in RAM.
• Cons: Introduces approximation error from compression. Distance calculations are approximate.

IVF is a clustering-based method that partitions the dataset into Voronoi cells.

• A coarse quantizer (like k-means) clusters the data. Each vector is assigned to its nearest centroid.
• At query time, the system finds the nprobe nearest centroids to the query and only searches within those corresponding cells.
• Often combined with Product Quantization (IVFPQ) for extreme compression.
• Pros: Very fast query speed when nprobe is small. Highly tunable trade-off between speed and recall via nprobe.
• Cons: Requires a training phase for clustering. Recall drops if the query's nearest neighbors are not in the probed cells.

HNSW is a state-of-the-art, graph-based ANN algorithm. It constructs a multi-layered graph where long-range connections on higher layers enable fast, logarithmic-time search, refined through short-range connections on lower layers.

• Key Strength: Often provides the best trade-off between speed, accuracy, and recall for in-memory indices.
• Wide Adoption: A default algorithm in libraries like Faiss and Weaviate.
• Mechanism: Inspired by small-world network theory, enabling 'navigable' graphs.

Inverted File Index (IVF) is a clustering-based ANN algorithm. It partitions the dataset using k-means clustering, creating Voronoi cells. Search is performed by comparing the query only to vectors in the nearest cell(s).

• Trade-off: Faster than brute-force but typically less accurate than HNSW for a given latency target.
• Combine with PQ: Often used with Product Quantization (PQ) for further compression and speed on disk.
• Use Case: Effective for very large datasets where memory footprint is a primary concern.

Product Quantization (PQ) is a compression technique for vectors that dramatically reduces memory footprint and accelerates distance calculations, often used in conjunction with ANN indexes like IVF.

• Mechanism: Splits a high-dimensional vector into sub-vectors, each quantized into a small set of centroids. A vector is represented by a short code of centroid IDs.
• Impact: Enables billion-scale vector indexes to fit in RAM by trading some precision.
• Distance Approximation: Uses lookup tables for fast, approximate distance computations.