Locality-Sensitive Hashing

Locality-Sensitive Hashing (LSH) is an approximate nearest-neighbour (ANN) technique that hashes high-dimensional vectors into discrete buckets such that nearby vectors have a high probability of colliding (hashing to the same bucket) and distant vectors collide with low probability. The technique was introduced by Piotr Indyk and Rajeev Motwani in their 1998 STOC paper “Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality” and developed further in many subsequent works. LSH was the dominant ANN technique through the 2000s and into the early 2010s, and it provides clean theoretical guarantees on query complexity. In modern practice, LSH has been largely displaced for general dense-vector ANN by HNSW and Product Quantization-based methods, which empirically achieve higher recall at lower latency. LSH remains used in specific settings where its properties (theoretical guarantees, distributed-friendliness, support for non-Euclidean distances) outweigh the modern alternatives’ empirical advantages.

1. The LSH Concept

The core idea: design a family of hash functions H such that, for any two vectors u, v ∈ ℝ^d:

• If ||u − v|| < r₁ (close), then Pr[h(u) = h(v)] ≥ p₁ for h ~ H.
• If ||u − v|| > r₂ (far), then Pr[h(u) = h(v)] ≤ p₂ for h ~ H.
• With p₁ > p₂ and r₁ < r₂.

A hash family with this property is called (r₁, r₂, p₁, p₂)-sensitive. The exact p₁ and p₂ depend on the family.

To search: hash each database vector with L independently-drawn hash functions from H, building L hash tables. At query time, hash the query with the same L functions; collect the union of vectors that collide with the query in any of the tables; compute exact distances on this union and return the top-K.

The search is sub-linear in dataset size (the expected number of collisions is small for a far query) and provides probabilistic guarantees on recall.

2. Hash Family Examples

Random projection LSH (cosine similarity). For a vector v, compute h(v) = sign(w · v) where w is a random Gaussian vector. The probability that two vectors hash to the same bit is 1 − θ/π where θ is the angle between them. With K random projections concatenated, vectors get a K-bit hash; nearby vectors in cosine sense are likely to share many bits.

MinHash (Jaccard similarity). For sets, MinHash uses random permutations and takes the minimum element. The probability that two sets have the same MinHash is the Jaccard similarity of the sets. MinHash is a foundational technique for set-similarity ANN; widely used in deduplication and clustering.

P-stable LSH (Lp norms). Uses random projections with stable distributions (Gaussian for L2, Cauchy for L1). Nearby vectors in the relevant norm have correlated projection values.

3. The Compound Hashing Trick

A single LSH function is too weak — many vectors collide that are not actually close. The standard construction uses two levels:

AND construction: concatenate K LSH functions to make a single K-tuple hash. Vectors collide on the K-tuple only if all K underlying hashes agree, which is rare for distant vectors. This sharpens the discrimination.

OR construction: use L different K-tuple hash tables. A vector pair is considered a candidate match if it collides in any of the L tables. This recovers recall lost from the AND construction.

The combined (K, L) parameterization gives a sharp recall-precision trade-off. Tuning to the desired operating point is part of the engineering work.

4. Why LSH Has Been Largely Displaced

In the 2010s, several developments shifted the ANN landscape:

Graph-based methods (HNSW) consistently outperform LSH on benchmark datasets, with higher recall at lower query latency.

Quantization-based methods (Product Quantization) offer better memory efficiency and similar recall.

Theoretical-vs-empirical gap. LSH’s clean theoretical guarantees do not translate to clean empirical wins; the constants in the analysis are often pessimistic, and the practical methods (HNSW, PQ) win in benchmarks despite weaker theory.

LSH still has niches:

• Distributed systems where the hash-table structure is naturally shardable.
• Set similarity (MinHash) where graph-based methods do not directly apply.
• Streaming or online indexing where the hash structure can be updated incrementally.

5. When to Use LSH

LSH is appropriate when:

• You need theoretical guarantees on recall (some applications require this).
• The data is non-vector (sets, sequences) and you can find an LSH family for the relevant similarity.
• The system architecture favors hash-table-based lookups (distributed databases, streaming systems).

For general dense-vector recommendation retrieval, HNSW or IVF-PQ (see FAISS) are usually preferred.

6. Strengths

• Theoretical guarantees on query complexity.
• Distributed-friendly — hash tables are naturally shardable.
• Supports non-Euclidean similarities (Jaccard, cosine, etc.).
• Streaming-compatible — vectors can be added incrementally.

7. Weaknesses

• Outperformed empirically by HNSW and PQ-based methods on dense-vector ANN.
• Hyperparameter tuning of (K, L) is non-trivial.
• Memory overhead of multiple hash tables.

8. See Also

• HNSW — modern graph-based alternative
• FAISS — supports LSH alongside other methods
• Product Quantization — alternative compression
• Inverted File Index — alternative partitioning
• Two-Tower Retrieval Model — recommender consumer
• Recommender Algorithms Catalog
• Recommender Systems