Approximate Nearest Neighbor (ANN) Search

ANN algorithms fundamentally exchange perfect recall for sub-linear query times. Instead of an exhaustive O(n) comparison against every vector, they navigate a pruned graph or hash bucket structure. The recall rate—typically 95-99.9%—is a tunable parameter. Increasing the search scope improves accuracy but increases latency, allowing engineers to define a service-level objective (SLO) that balances precision against queries per second (QPS).

The Hierarchical Navigable Small World (HNSW) algorithm constructs a multi-layered graph where long-range edges on sparse upper layers enable logarithmic scaling. A greedy search traverses from the top layer downward, finding the nearest neighbor in each layer before descending. This structure provides state-of-the-art performance for high-recall scenarios without requiring a separate training phase, though it consumes significant memory to store the graph edges.

The Inverted File index partitions the vector space into clusters using k-means. At query time, only the nearest nprobe clusters are searched exhaustively. This reduces the search scope dramatically. Key characteristics:

• Training required: A clustering pass over a representative sample of data.
• Memory efficiency: Only cluster centroids and vector assignments are stored.
• Product Quantization (PQ) is often combined with IVF to compress the vectors within each cluster, enabling billion-scale search in RAM.

LSH uses hash functions designed so that similar vectors collide in the same bucket with high probability. The query vector is hashed, and only vectors in the same bucket are compared. Multiple hash tables are used to boost recall. While conceptually elegant and offering strong theoretical guarantees, LSH often requires more memory and provides lower recall than graph-based methods for high-dimensional embeddings, making it less common in modern vector databases.

To fit billion-scale datasets in memory, ANN indexes employ vector compression. Product Quantization (PQ) splits a vector into sub-vectors and quantizes each independently, reducing a 1024-dimensional float32 vector from 4KB to ~64 bytes. Scalar Quantization (SQ) converts floats to 8-bit integers. These compressed representations allow distance calculations to be performed efficiently using lookup tables, trading a small amount of precision for dramatic memory savings.

Real-world retrieval rarely relies on vector similarity alone. ANN systems support pre-filtering (applying metadata constraints before vector search) and post-filtering (searching vectors first, then filtering). Pre-filtering can miss results if the filter eliminates all candidates in a cluster. Advanced engines implement filter-aware indexing that integrates metadata into the graph traversal itself, ensuring accurate top-k results even under strict attribute constraints.

A measure of similarity between two non-zero vectors that calculates the cosine of the angle between them. It ranges from -1 (completely opposite) to 1 (identical direction), with 0 indicating orthogonality. Why it matters for ANN:

• The most common distance metric for text embeddings and semantic search
• Magnitude-invariant, focusing purely on directional alignment
• Efficiently computed via dot product when vectors are L2-normalized

A metric that measures the number of bit positions where two binary strings of equal length differ. In ANN contexts, it is used to compare compact binary hash codes generated by techniques like LSH or deep hashing. Advantages:

• Computed via XOR and popcount operations, making it extremely fast on modern CPUs
• Enables efficient exact search in Hamming space using multi-index hashing
• Commonly used in near-duplicate detection systems where hashes are 64-bit or 128-bit SimHash fingerprints

A class of methods that use deep neural networks to learn compact binary hash codes directly from data. Unlike traditional LSH, deep hashing jointly optimizes feature extraction and quantization. Architecture patterns:

• Siamese networks with contrastive or triplet loss to preserve semantic similarity in Hamming space
• End-to-end training minimizes quantization error while maximizing inter-class separation
• Produces highly compact codes (32-128 bits) that outperform hand-crafted hashing on complex data like images and audio

Specialized storage and retrieval systems designed to index high-dimensional embeddings for rapid semantic search. These systems combine ANN algorithms with persistent storage, metadata filtering, and horizontal scaling. Operational capabilities:

• Hybrid search combining vector similarity with structured metadata filters
• Real-time index updates for streaming data ingestion
• Namespace isolation for multi-tenant deployments
• Examples include Pinecone, Weaviate, Milvus, and Qdrant