Locality-Sensitive Hashing (LSH)

The defining property of LSH: similar items collide in the same bucket with high probability, while dissimilar items are mapped to different buckets. This is formalized through a distance-sensitive family of hash functions where the collision probability Pr[h(x) = h(y)] = sim(x, y). For cosine similarity, random hyperplane projections achieve this; for Jaccard similarity, MinHash provides the guarantee. The probability curve creates a sharp threshold—items above a similarity cutoff almost certainly collide, while those below almost never do.

LSH controls precision and recall through banding techniques that combine multiple hash functions:

• AND construction (r rows): Concatenating r hash values into a single signature reduces false positives by requiring agreement across all r functions
• OR construction (b bands): Using b independent hash tables reduces false negatives by allowing a match in any band
• The S-curve effect: The AND-OR composition creates a steep sigmoid probability curve, giving near-certain collision above a tunable similarity threshold and near-zero collision below it

LSH achieves O(n^ρ) query time where ρ < 1, dramatically outperforming brute-force O(n) linear scans. For a dataset of 1 billion vectors, an LSH index with ρ = 0.5 reduces comparisons from 1 billion to approximately 31,600. The parameter ρ is determined by the hash family's sensitivity and the desired similarity threshold. This sublinear scaling is what makes LSH viable for billion-scale nearest neighbor search in production systems like image retrieval and recommendation engines.

LSH families are designed for specific distance metrics, each with distinct hash constructions:

• Cosine similarity: Random projection using a random hyperplane; the sign of the dot product determines the hash bit
• Jaccard similarity: MinHash uses the minimum hash value of set elements under random permutations
• Euclidean distance (L2): p-stable distributions (e.g., Gaussian) project points onto random lines, then quantize into buckets
• Hamming distance: Bit sampling directly selects random bit positions
• Earth Mover's Distance: Specialized embeddings for distributional similarity

A hash family H is (d₁, d₂, p₁, p₂)-sensitive if for any two points:

• If d(x, y) ≤ d₁, then Pr[h(x) = h(y)] ≥ p₁
• If d(x, y) ≥ d₂, then Pr[h(x) = h(y)] ≤ p₂ Where p₁ > p₂ and d₁ < d₂. This formal guarantee ensures a gap between the collision probability of close and far points. The amplification gap (p₁ vs p₂) determines how effectively AND-OR construction can separate similar from dissimilar pairs, with larger gaps enabling more efficient indexes.

LSH functions as a pre-filter for exact distance computation, not a replacement. The workflow:

1. Hash the query point into all LSH tables
2. Retrieve all items that share at least one bucket with the query (candidate pairs)
3. Compute exact distances only on candidates, typically reducing comparisons by 99% or more
4. Return the k-nearest verified neighbors This two-phase approach guarantees exact results on the filtered set while avoiding the prohibitive cost of exhaustive comparison across the entire dataset.

A fundamental metric for comparing binary hash codes generated by LSH. It measures the number of bit positions where two equal-length strings differ.

• Calculation: XOR two binary strings, count the set bits
• LSH Context: Used when LSH outputs compact binary codes; similar items have a small Hamming distance
• Example: The binary strings 101010 and 101110 have a Hamming distance of 1
• Efficiency: Computable in O(1) with hardware-level POPCNT instructions on modern CPUs

The most common similarity measure used in conjunction with LSH for comparing dense vector embeddings from neural networks.

• Definition: Measures the cosine of the angle between two non-zero vectors, ranging from -1 (opposite) to 1 (identical)
• LSH Families: Random hyperplane LSH uses random projections to hash vectors based on which side of a hyperplane they fall on
• Scale Invariance: Unlike Euclidean distance, cosine similarity ignores vector magnitude, focusing purely on directional alignment
• Use Case: Dominant in semantic search systems comparing BERT or GPT embeddings

A specific LSH scheme optimized for estimating the Jaccard similarity between sets, widely used for document deduplication.

• Mechanism: Applies multiple hash functions to a set's elements and keeps only the minimum hash value from each function
• Property: The probability that two sets share the same MinHash value equals their Jaccard similarity
• Band Partitioning: MinHash signatures are split into bands to amplify the probability of collision for similar sets
• Application: Powers near-duplicate detection in web crawling and plagiarism checking systems

A dimensionality reduction technique that produces a compact fingerprint where similar documents yield hashes with a small Hamming distance.

• Algorithm: Weights each feature of a document by its TF-IDF score, then collapses the weighted vector into a binary fingerprint
• Key Property: Similar documents produce fingerprints differing in only a few bits, enabling efficient near-duplicate detection
• Google's Use: Famously employed in Google's web crawler to detect duplicate pages at scale
• Difference from MinHash: SimHash works on weighted feature vectors, while MinHash operates on sets

The broader problem that LSH is designed to solve, trading a small amount of accuracy for dramatic speed improvements in high-dimensional spaces.

• The Curse of Dimensionality: Exact nearest neighbor search degrades to linear scan in high dimensions
• LSH as an Index: LSH serves as the indexing layer, partitioning the vector space so only a few buckets need to be searched
• Alternative ANN Methods: Graph-based (HNSW), tree-based (Annoy), and quantization-based (IVF) approaches
• Performance Trade-off: LSH offers sub-linear query time with probabilistic guarantees on recall