Locality-Sensitive Hashing

Locality-Sensitive Hashing (LSH) is a randomized algorithmic framework in computation and algorithms and high-dimensional computational geometry for solving the (c, r)-Approximate Nearest Neighbor (ANN) search problem in sublinear query time O(d · n^ρ) with exponent ρ < 1. Formulated by Piotr Indyk and Rajeev Motwani in their seminal 1998 STOC paper "Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality," LSH reverses the design objective of classical and cryptographic hash function families: instead of scattering similar inputs uniformly across buckets to minimize collisions in a hash table, a locality-sensitive hash family H is explicitly constructed so that the probability of a hash collision Pr_h∈H[h(p) = h(q)] increases monotonically as the distance d(p, q) between two points decreases.

In low dimensions (d ≤ 10), true nearest-neighbor search in an n-point dataset can be solved in O(log n) query time using spatial partitioning trees (k-d trees, R-trees, or Voronoi diagrams). However, as dimension d grows into hundreds or thousands (such as vector embeddings, genomic k-mer profiles, or image descriptors), the curse of dimensionality causes the volume of a high-dimensional sphere to concentrate near its boundary and causes spatial tree searches to degrade to an O(d · n) exhaustive linear scan. By relaxing true nearest-neighbor search to c-approximate search (for c > 1) and combining metric-specific LSH families—such as bit sampling for Hamming distance, MinHash for Jaccard distance, SimHash random hyperplanes for cosine similarity, and p-stable projections for Euclidean L₂ distance—LSH guarantees query time whose exponent ρ = ln(1/P₁) / ln(1/P₂) depends only on the approximation ratio c and is independent of the ambient dimension d.

Definition of an LSH Family

Let (X, d) be a metric space and let U be a hash bucket universe. A family H = {h : X → U} of hash functions Equipped with a probability distribution is called (r₁, r₂, P₁, P₂)-sensitive (with r₁ < r₂ and P₁ > P₂) if for every pair of points p, q ∈ X:

1. High Collision Probability for Close Points: If d(p, q) ≤ r₁, then Pr_h∈H[ h(p) = h(q) ] ≥ P₁.
2. Low Collision Probability for Far Points: If d(p, q) ≥ r₂ = c · r₁, then Pr_h∈H[ h(p) = h(q) ] ≤ P₂.

The efficiency of an (r₁, c r₁, P₁, P₂)-sensitive family is governed by the dimensionless LSH quality exponent:

Because P₁ > P₂ ∈ (0, 1), we have 0 < ln(1/P₁) < ln(1/P₂), ensuring ρ < 1.

Indyk–Motwani AND-Then-OR Amplification Construction

A single hash function h ∈ H typically has a modest gap between P₁ and P₂ (for instance, P₁ = 0.8 and P₂ = 0.5). To amplify this probability gap into a sharp step function, Indyk and Motwani apply a two-stage (k, L) AND–OR concatenation:

1. AND Concatenation (Widening the Gap): Concatenate k independent base hash functions from H to form a compound vector hash function g(x) = (h₁(x), h₂(x), ..., h_k(x)). Two points collide under g (g(p) = g(q)) if and only if they collide in all k coordinates, lowering the false-positive collision probability for far points (d(p, q) ≥ r₂) to P₂^k. Choosing k = ⌈ log_1/P2 n ⌉ = ⌈ (ln n) / ln(1/P₂) ⌉ ensures that P₂^k ≤ 1 / n, so the expected number of far points (d ≥ r₂) colliding with query q in a single table g is at most n · (1/n) = 1 point.
2. OR Repetition (Restoring Recall): Because AND concatenation also lowers the true-positive collision probability for a close neighbor (d(p, q) ≤ r₁) to P₁^k = P₁^{(ln n)/ln(1/P₂)} = n^{−ln(1/P₁)/ln(1/P₂)} = n^−ρ, the algorithm constructs L = ⌈ n^ρ ⌉ independent hash tables g₁, g₂, ..., g_L.

During a query for q, the algorithm probes the L buckets g₁(q), ..., g_L(q) and inspects at most 3L candidate points. The probability of finding a close neighbor p (d(p, q) ≤ r₁) across the L tables is at least 1 − (1 − n^−ρ)^nρ ≥ 1 − 1/e ≈ 0.632 (boosted to 1 − δ by scaling L by ln(1/δ)). Thus, LSH achieves query time O(d · n^ρ log n) and space O(n^1+ρ + d · n).

Each distance metric admits a mathematically tailored LSH family whose collision probability is a closed-form function of distance or similarity:

• Hamming Space ({0, 1}^d, d_H) — Bit Sampling (Indyk & Motwani, 1998): Pick a random coordinate i ∈ {1, ..., d} and set h_i(x) = x_i. Then Pr[h(p) = h(q)] = 1 − d_H(p, q) / d, achieving exponent ρ ≤ 1 / c.
• Jaccard Distance (J(A, B)) — MinHash (Broder, 1997): For sets A, B ⊆ U, h_π(A) = min_x∈A π(x) satisfies Pr[h_π(A) = h_π(B)] = J(A, B) = 1 − d_J(A, B).
• Angular / Cosine Similarity (θ(p, q)) — Random Hyperplane SimHash (Charikar, 2002): Sample a unit Gaussian vector v ~ N(0, I_d) and set h_v(x) = sign(v · x) ∈ {−1, +1}. Because the probability that a random hyperplane separates p and q is proportional to the angle θ = arccos((p · q) / (‖p‖₂ ‖q‖₂)) between them, the collision probability is:

• Euclidean & L_p Distance (p ∈ (0, 2]) — p-Stable Projections E2LSH (Datar et al., 2004): Project x ∈ ℝ^d onto a vector a whose entries are drawn i.i.d. from a p-stable distribution (standard Gaussian N(0, 1) for L₂ Euclidean distance; Cauchy distribution for L₁ Manhattan distance) and quantize into bins of width w with random shift b ~ Uniform[0, w]:

achieving exponent ρ ≈ 1 / c for L₁ and ρ ≈ 1 / c² for L₂ via Cross-Polytope / Spherical LSH (Andoni & Indyk, 2006; Andoni et al., 2015).

A practical drawback of basic (k, L) LSH is that constructing L = O(n^ρ) separate hash tables requires significant memory when ρ ≈ 0.3–0.5. In 2007, Qin Lv, William Josephson, Zhe Wang, Moses Charikar, and Kai Li introduced Multi-Probe LSH, which observes that in quantized Euclidean LSH (h_a,b(x) = ⌊(a · x + b)/w⌋), a close neighbor p that misses the exact query bucket g(q) almost always lands in an adjacent bucket differing by ±1 in one or two coordinates. By probing a sequence of perturbation vectors around g(q) within each table, Multi-Probe LSH reduces the required number of hash tables L by an order of magnitude (~90% memory reduction) at identical recall.

On the theoretical frontier, Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya Razenshteyn, and Ludwig Schmidt (2015) proved that Cross-Polytope LSH (rotating x on the unit sphere via fast Hadamard transforms and snapping to the nearest vertex ±e_i of the cross-polytope) achieves the optimal data-independent Euclidean exponent ρ = 1 / c², and that data-dependent LSH reduces the exponent further to ρ = 1 / (2c² − 1). In deep learning and bioinformatics, Cross-Polytope LSH powers the Reformer transformer architecture (Kitaev, Kaiser, & Levskaya, 2020)—reducing self-attention complexity from O(L²) to O(L log L) by computing attention only among query-key vectors that collide in the same LSH bucket—and accelerates long-read genome assembly (MHAP, Berlin et al., 2015) alongside Bloom filter and Count–Min sketch indexes.

Why does locality-sensitive hashing require distinct hash families for different distance metrics?

In fact, a metric space (X, d) admits an LSH family if and only if (X, d) can be isometrically (or low-distortion) embedded into L₁ or Hamming space. For example, no LSH family can exist for the general L_∞ (Chebyshev) norm without polynomial distortion depending on d, because L_∞ cannot be embedded into L₁ without Ω(log d) distortion. Consequently, each metric (L₁, L₂, Cosine, Jaccard) requires an LSH construction tailored to its specific geometric isometries.

How does Google's 64-bit SimHash detect near-duplicate web pages across billions of URLs?

In Moses Charikar's SimHash (deployed at Google by Manku, Jain, & Das Sarma, 2007), each weighted document feature f is hashed to a 64-bit string and adds +w_f (for 1-bits) or −w_f (for 0-bits) to a 64-element accumulator vector; taking the signs yields a 64-bit fingerprint. Two 64-bit fingerprints across an 8-billion-page corpus are tested for Hamming distance d_H ≤ 3 in sub-millisecond time by splitting the 64 bits into blocks and probing a few permuted prefix tables.

How does LSH compare with graph-based ANN indexes like HNSW (Hierarchical Navigable Small World) in practice?

Graph-based proximity indexes (such as HNSW and DiskANN) and product quantization (FAISS IVF-PQ) achieve higher empirical recall-per-second on moderate-dimensional dense neural embeddings (d = 128–1,536) by exploiting the low intrinsic dimensionality of real data manifolds, but require expensive O(n log n) index construction and lack worst-case theoretical guarantees. By contrast, LSH offers provable worst-case sublinear query bounds, O(1) streaming insertions/deletions without graph rebuilding, and unmatched speed for sparse/set representations (via MinHash) and on-the-fly dynamic bucketing (such as Reformer LSH attention).

1. Indyk, P., & Motwani, R. (1998). "Approximate nearest neighbors: towards removing the curse of dimensionality." Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing (STOC '98), 604–613. https://doi.org/10.1145/276698.276876
2. Charikar, M. S. (2002). "Similarity estimation techniques from rounding algorithms." Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing (STOC '02), 380–388. https://doi.org/10.1145/509907.509965
3. Datar, M., Immorlica, N., Indyk, P., & Mirrokni, V. S. (2004). "Locality-sensitive hashing scheme based on p-stable distributions." Proceedings of the Twentieth Annual Symposium on Computational Geometry (SoCG '04), 253–262. https://doi.org/10.1145/997817.997857
4. Lv, Q., Josephson, W., Wang, Z., Charikar, M., & Li, K. (2007). "Multi-probe LSH: efficient indexing for high-dimensional similarity search." Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB '07), 950–961. https://dl.acm.org/doi/10.5555/1325851.1325958
5. Andoni, A., Indyk, P., Laarhoven, T., Razenshteyn, I., & Schmidt, L. (2015). "Practical and optimal LSH for angular distance." Advances in Neural Information Processing Systems (NeurIPS 28), 1225–1233. https://proceedings.neurips.cc/paper/2015/file/2823f4797102ce1a1aec05359cc16dd9-Paper.pdf