Locality-Sensitive Hashing (LSH)

Unlike cryptographic hashes that maximize the avalanche effect, LSH functions are designed so that the probability of two items colliding in the same bucket increases as their similarity increases. Formally, for a distance measure D and thresholds d1 < d2, a hash family H is locality-sensitive if Pr[h(x) = h(y)] is high when D(x,y) < d1 and low when D(x,y) > d2. This is the fundamental property that enables sub-linear search by grouping similar vectors together.

A single LSH function is often too weak to be useful. Amplification combines multiple functions to tune precision and recall:

• AND-construction (banding): Concatenating k independent hash functions into a single signature. This decreases false positives by requiring agreement across all k dimensions.
• OR-construction: Creating L independent hash tables. This increases recall by providing multiple independent chances for a true neighbor to collide. The combination of k ANDs and L ORs creates the (k, L) parameterized LSH family, allowing engineers to trade off between precision and recall.

LSH families are mathematically tailored to specific distance measures. The choice of hash family must match the similarity metric used in the embedding space:

• Jaccard Similarity: MinHash uses random permutations to estimate set overlap.
• Cosine Similarity: SimHash (Signed Random Projections) uses a random hyperplane; the sign of the dot product determines the hash bit.
• Euclidean Distance (L2): p-stable distributions (e.g., Gaussian) project points onto random lines, then quantize the projection into buckets of width w.
• Hamming Distance: Bit sampling directly uses a subset of bits as the hash.

The primary computational advantage of LSH is reducing similarity search from O(N) to sub-linear time. By hashing the query vector and only examining items that fall into the same bucket, LSH avoids a full scan of the dataset. The theoretical query time is typically O(N^ρ), where ρ < 1 is a function of the approximation factor c. For example, with Hamming distance, ρ = 1/c. This makes LSH the foundational algorithmic primitive behind scalable vector databases and approximate nearest neighbor (ANN) systems.

Classic LSH is data-independent: the hash functions are drawn randomly from a known distribution without analyzing the dataset. This provides strong theoretical guarantees on worst-case performance. In contrast, modern data-dependent methods like HNSW or learned hashing analyze the data distribution to build more efficient partitions, often achieving better empirical performance but without the same theoretical guarantees. LSH remains critical in streaming and dynamic settings where the index must be updated without full retraining.

LSH performance is governed by a critical trade-off controlled by k (hash length) and L (number of tables):

• Increasing k: Raises precision by requiring stricter agreement, but lowers recall as true neighbors may disagree on at least one bit.
• Increasing L: Boosts recall by providing more collision opportunities, but increases memory and query time linearly. The optimal (k, L) configuration is typically found through grid search over a validation set, balancing the target recall (e.g., 0.95) against the acceptable query latency budget.

A metric measuring the cosine of the angle between two non-zero vectors, used to quantify semantic similarity irrespective of vector magnitude. LSH families like SimHash and random projection are specifically designed to preserve cosine similarity in the hashed space. - Normalized vectors: cosine similarity equals inner product - LSH for cosine: uses random hyperplanes to partition space - Essential for semantic search and deduplication tasks

A vector compression technique that decomposes the original high-dimensional space into a Cartesian product of lower-dimensional subspaces and quantizes each separately. LSH + PQ is a common hybrid architecture: LSH provides fast coarse filtering, while PQ enables memory-efficient storage of the candidate vectors. - Reduces memory footprint by 10-30x - Often combined with inverted file indexing (IVF-PQ) - Critical for billion-scale vector databases

A phenomenon where distance metrics become less meaningful as dimensions increase, degrading traditional indexing performance. LSH directly addresses this by projecting high-dimensional vectors into lower-dimensional hash codes where collisions remain meaningful. Key insight: in high dimensions, all points appear equidistant; LSH breaks this by focusing on local-sensitive hash collisions rather than exact distance calculations.

A graph-based ANN algorithm that builds a multi-layered navigable structure for logarithmic-time retrieval. While HNSW often achieves higher recall than LSH for in-memory datasets, LSH remains superior for: - Disk-based indexes where graph traversal is expensive - Streaming deduplication requiring constant-time lookups - Privacy-preserving search using cryptographic hash properties

A metric measuring overlap between two sets, defined as the size of the intersection divided by the size of the union. MinHash LSH is specifically designed to preserve Jaccard similarity, making it ideal for: - Document near-duplicate detection - Plagiarism identification - Set-based feature matching in recommendation systems - MinHash uses k independent hash functions to create compact signatures