Approximate Nearest Neighbor (ANN) Search

Hierarchical Navigable Small World (HNSW) is a state-of-the-art graph-based ANN algorithm. It constructs a multi-layered graph where each layer is a subset of the previous one, with long-range connections on higher layers and short-range connections on lower layers.

• Search Process: Begins at the top layer with a random entry point, greedily traverses to the nearest neighbor, then moves down a layer using that point as the new entry, repeating until the bottom layer.
• Key Advantages: Provides very high recall (>95%) with sub-millisecond query times for million-scale datasets. It supports dynamic insertions and deletions efficiently.
• Implementation: Forms the core indexing method in vector databases like Weaviate, Qdrant, and Vespa, and is available in libraries like FAISS.

Inverted File (IVF) is a clustering-based indexing method that partitions the vector space into Voronoi cells using a clustering algorithm like k-means.

• Search Process: During a query, the system identifies the nprobe closest clusters (cells) to the query vector and performs an exhaustive search only within the vectors assigned to those clusters.
• Trade-off: Speed is controlled by the nprobe parameter (number of cells to search). Higher nprobe increases accuracy and latency.
• Optimization: Often combined with Product Quantization (PQ) for further compression, creating the IVF-PQ index, which is highly memory-efficient for billion-scale datasets. This is a foundational algorithm in the FAISS library.

Locality-Sensitive Hashing (LSH) is a probabilistic hashing technique designed so that similar items map to the same hash buckets with high probability.

• Core Principle: Uses hash functions that are 'sensitive' to distance; vectors that are close in the original space have a high chance of colliding (getting the same hash).
• Process: Multiple hash tables are built with different hash functions. A query is hashed to retrieve candidate vectors from corresponding buckets, which are then filtered for the nearest neighbors.
• Use Case: Historically important for large-scale duplicate detection and similarity search in high dimensions. It is less commonly used for ultra-high recall applications compared to HNSW but remains valuable for certain streaming or distributed scenarios.

ANNOY (Approximate Nearest Neighbors Oh Yeah) is a library based on building a forest of binary trees to partition the vector space.

• Index Construction: Recursively splits the space using random hyperplanes, assigning vectors to child nodes, until a leaf node contains a small number of points.
• Search Process: Traverses multiple trees in the forest to collect candidate points from the leaf nodes where the query lands, then computes exact distances to these candidates.
• Characteristics: Provides a good trade-off between build time, accuracy, and memory usage. It is static (not designed for frequent updates) and is known for its simplicity and effectiveness, famously used at Spotify for music recommendations.

Quantization techniques reduce the memory footprint of vectors, enabling billion-scale indexes to fit in RAM. They are almost always used in conjunction with other indexing methods like IVF.

• Product Quantization (PQ): Splits the high-dimensional vector into sub-vectors and quantizes each sub-space independently using a small codebook. A vector is represented by a short code of centroid IDs.
• Scalar Quantization (SQ): Reduces the precision of each vector component (e.g., from 32-bit floats to 8-bit integers).
• Impact: Quantization allows searching vastly larger datasets in memory but introduces approximation error. Distance calculations are performed using lookup tables for speed. The FAISS IVF-PQ index is the canonical example.

Modern vector databases implement hybrid search by combining ANN with traditional metadata filtering.

• Pre-Filtering: Apply metadata filters (e.g., user_id = 123) first, then perform ANN search on the filtered subset. This can be inefficient if the filter is highly selective.
• Post-Filtering: Perform ANN search on the full dataset, then filter the results. This can discard too many relevant results.
• Single-Stage Filtered Search: Advanced indexes like HNSW can integrate filter conditions directly into the graph traversal, checking candidate eligibility during the search. This is implemented in databases like Qdrant and Weaviate and is crucial for real-world applications where retrieval must respect business logic.

HNSW is a graph-based ANN algorithm that constructs a multi-layered graph where each layer is a subset of the layer below. It enables highly efficient search by starting at the top layer (with few nodes) to find an approximate region, then navigating down through the layers to refine the result.

• Key Property: Provides a strong trade-off between high recall, low latency, and reasonable memory usage.
• Usage: The default or highly recommended index in many vector databases (e.g., Weaviate, Qdrant, Pinecone) and libraries like FAISS.

FAISS is an open-source library developed by Meta AI for efficient similarity search and clustering of dense vectors. It is not a single algorithm but a toolkit implementing various ANN methods.

• Core Indexes: Includes IVF (Inverted File Index) for coarse quantization, Product Quantization (PQ) for memory compression, and HNSW.
• Key Feature: Allows GPU acceleration for massive-scale search (billions of vectors).
• Typical Use: Served as a backend library within custom ML pipelines or embedding-serving infrastructure.

LSH is a family of hashing techniques designed so that similar input items map to the same hash buckets with high probability. It's a classic ANN approach that reduces search complexity by hashing vectors into lower-dimensional signatures.

• Mechanism: Uses randomized hash functions where the probability of collision is proportional to the similarity of the items.
• Trade-off: Often faster to build than graph-based indexes but may require more memory for high recall and can be less accurate than HNSW for high-dimensional data.
• Use Case: Found in older or specialized systems; useful for understanding the fundamental theory of approximate search.

IVF is a clustering-based indexing method commonly used within FAISS. It partitions the vector space into Voronoi cells via k-means clustering. Each cell is represented by a centroid, and vectors are assigned to their nearest centroid.

• Search Process: For a query, the system finds the nearest centroids (coarse quantizer), then performs an exact search only within the vectors belonging to those cells.
• Advantage: Dramatically reduces the search space. Often combined with Product Quantization (IVFPQ) to also compress vector storage.
• Parameter: nprobe controls how many cells are searched, balancing speed and accuracy.

Product Quantization is a compression technique for vectors that reduces memory footprint, enabling billion-scale datasets to fit in RAM. It is frequently combined with IVF (as IVFPQ).

• Mechanism: Splits a high-dimensional vector into subvectors, each quantized independently using a small codebook. The original vector is represented by a concatenation of codebook indices.
• Effect: Allows an approximate distance between the query and a database vector to be computed using lookup tables, which is very fast.
• Trade-off: Introduces quantization error, reducing accuracy for significant gains in memory efficiency and speed.

Reranking is a two-stage retrieval pipeline that combines the speed of ANN with the accuracy of more powerful models. An ANN system (e.g., using a bi-encoder) fetches a broad set of candidates (e.g., top 100), which are then precisely re-scored by a slower, more accurate cross-encoder model.

• Cross-Encoder: Processes the query and candidate text together with full attention, producing a highly accurate relevance score.
• System Benefit: Achieves near-perfect precision for the final top results (e.g., top 10) while maintaining the low-latency, scalable front-end provided by ANN search.
• Industry Practice: A standard pattern in production Retrieval-Augmented Generation (RAG) systems.