Approximate Nearest Neighbor (ANN)

ANN algorithms fundamentally exchange perfect recall for sub-linear query times. Instead of scanning every vector (O(n) brute force), they prune the search space. The recall rate—typically 95-99%—is the metric defining how many true nearest neighbors are returned. This trade-off is controlled by hyperparameters like ef_search in HNSW or nprobe in IVF indexes, allowing engineers to dial precision up or down based on latency budgets.

The Hierarchical Navigable Small World algorithm constructs a multi-layered proximity graph where long-range edges exist in upper layers and short-range edges in lower layers. Search begins at the topmost layer for coarse-grained navigation and descends greedily. This structure achieves O(log n) complexity and dominates benchmarks due to its high recall at low latency. Key parameters:

• M: Number of bi-directional links per node (controls memory vs. accuracy)
• ef_construction: Beam width during index building
• ef_search: Beam width during query time

IVF partitions the vector space into Voronoi cells using k-means clustering. At query time, only the nprobe closest clusters are searched exhaustively. This coarse quantization acts as a pre-filter, reducing the search scope by orders of magnitude. IVF is often paired with Product Quantization (PQ) for compression, where residual vectors are encoded as compact codes. The combination—IVFPQ—enables billion-scale search on memory-constrained hardware by storing compressed representations in RAM.

LSH uses a family of hash functions designed so that similar vectors collide in the same bucket with high probability. Random projection planes partition the space; vectors on the same side of a plane share a hash bit. By concatenating multiple hash functions into a compound key, LSH builds hash tables where candidates are retrieved in constant time. While historically foundational, LSH often requires more memory and yields lower recall than graph-based methods for high-dimensional embeddings, though it remains valuable for streaming and distributed settings.

Spotify's ANNOY (Approximate Nearest Neighbors Oh Yeah) builds a forest of random projection trees. Each tree recursively splits the vector space with random hyperplanes, creating binary partitions. At query time, the forest is traversed simultaneously, and a priority queue merges candidates from all trees. ANNOY uses memory-mapped files, allowing indexes larger than RAM to be served from disk. It trades some recall for extremely fast build times and static index immutability, making it suitable for read-heavy, infrequently updated datasets.

To fit billion-scale indexes in memory, ANN systems employ aggressive compression:

• Product Quantization (PQ): Splits vectors into sub-vectors, clusters each subspace independently, and stores cluster IDs instead of floats. A 128-dim float32 vector (512 bytes) can be compressed to 64 bytes.
• Scalar Quantization (SQ): Maps each float dimension to an 8-bit integer range, achieving 4x compression with minimal accuracy loss.
• Binary Embeddings: Binarizes vectors to single bits, enabling Hamming distance computation via XOR and popcount CPU instructions for extreme speed.

A vector compression technique that decomposes high-dimensional vectors into smaller sub-vectors and quantizes them independently, drastically reducing memory footprint for ANN search.

• Splits a D-dimensional vector into M sub-vectors of dimension D/M
• Each sub-vector is quantized using a separate codebook of k centroids
• Compression ratio example: 1024-dim float32 vector (4096 bytes) → 64 bytes with M=64, k=256
• Enables billion-scale vector search in RAM
• Introduces a small but measurable recall loss due to quantization error

An algorithmic technique that hashes similar input items into the same buckets with high probability, enabling fast approximate similarity search in massive datasets.

• Uses hash functions designed so collision probability increases with input similarity
• Common implementations: random projection for cosine similarity, p-stable distributions for Euclidean distance
• Sub-linear query time by only examining items in colliding buckets
• Theoretical guarantees on recall probability given hash parameters
• Largely superseded by graph-based methods in modern vector databases but remains foundational

A specialized data management system that indexes and queries high-dimensional vector embeddings while maintaining the stored data in an encrypted state to preserve cryptographic privacy.

• Combines ANN indexing with homomorphic encryption or searchable encryption primitives
• Allows similarity search over ciphertext without the server seeing plaintext vectors
• Critical for sovereign AI infrastructure where data residency and privacy are non-negotiable
• Performance overhead vs. plaintext ANN: typically 10-100x slower depending on encryption scheme
• Emerging implementations leverage Trusted Execution Environments as an alternative to pure cryptographic approaches

A dense, low-dimensional numerical representation of unstructured data—such as text or images—that captures semantic meaning and relationships in a continuous vector space.

• Generated by encoder models (e.g., BERT, CLIP, text-embedding-3)
• Typical dimensionality ranges from 384 to 4096 floating-point values
• Semantic similarity is measured via cosine similarity, Euclidean distance, or dot product
• The quality of ANN search is fundamentally bounded by the quality of the underlying embeddings
• Embedding drift over time requires periodic re-indexing to maintain search relevance