MinHash and LSH

Finding near-duplicate documents is a common problem. A crawler sees the same article on three sites with small edits, and you want to keep one. Comparing every pair of a billion documents is far too slow. MinHash turns each document into a small signature. Locality-sensitive hashing (LSH) uses those signatures to find similar pairs without checking every pair.

The big idea

MinHash relies on one fact. Apply a random ordering to every element, and take the smallest element of each set. The two minimums are equal exactly when the smallest element of the combined set is in both sets. So the chance of a match equals J(A, B).

Using many random orderings makes this an estimate you can measure. Each ordering gives one number per set. Together they form a signature.

Walking through one ordering

Take two sets with 5 items in total.

A = {a, b, c, d}
B = {b, c, d, e}
J(A, B) = |{b, c, d}| / |{a, b, c, d, e}| = 3 / 5 = 0.6

Give each item a random rank. Here is one ordering.

rank:  a=3  b=1  c=4  d=2  e=5
min over A = min(3, 1, 4, 2) = 1  → b
min over B = min(1, 4, 2, 5) = 1  → b
match: yes

Now try a second ordering, a=1, b=2, c=3, d=4, e=5. The minimum of A is a (rank 1), and the minimum of B is b (rank 2). They do not match. Over many random orderings, the match rate settles at about 0.6. In a simulation with 100,000 orderings, it came out at 0.599. That is the Jaccard similarity.

Signatures and their error

A document becomes a signature of 128 minimums, one per ordering. Two signatures are compared position by position. The share of positions that agree estimates J.

signature length     = 128 numbers × 4 bytes = 512 bytes
standard error       ≈ 1 / √128 ≈ 0.09
document size        ≈ 50 KB   →   signature 512 bytes

A 50 KB document shrinks to 512 bytes, with an error of about ±0.09 on the similarity estimate. Andrei Broder developed this at AltaVista in 1997 to find near-duplicate web pages.

Locality-sensitive hashing

Comparing all pairs of a billion signatures is still too slow. LSH banding avoids most comparisons. Split each 128-number signature into b = 32 bands of r = 4 numbers. Hash each band into a bucket. Two documents become a candidate pair only if they land in the same bucket for at least one band.

The chance that two documents with similarity s become candidates is:

P(candidate) = 1 − (1 − s^r)^b = 1 − (1 − s⁴)^32

The curve is an S shape. Its midpoint, the threshold, is about (1/b)^(1/r) = (1/32)^(1/4) ≈ 0.42. Very similar pairs almost always collide. Dissimilar pairs rarely do. Changing b and r moves the threshold, so you can tune the cutoff to match what counts as a duplicate.

Where it fits

• Near-duplicate detection in crawlers and search indexes. Keep one copy of each near-identical page.
• Similarity search across large collections of sets, such as shared tags or shared shingles.
• Vector search. The same idea works for embedding vectors. Random hyperplanes give each vector one bit, based on which side of the plane it falls. Two vectors agree on a bit with a probability that depends on the angle between them. Google has used a SimHash variant of this idea for near-duplicate web pages. Modern vector databases mostly use graph indexes instead, but the goal is the same: find close neighbors without comparing everything. See embeddings.

Common mistakes

• Comparing full documents pairwise. Build signatures, then band them.
• Using too few hash functions. The standard error is about 1 / √(number of hashes). Fewer hashes means noisier estimates.
• Picking b and r without checking the threshold. Compute the S-curve for your choice and check where it crosses the duplicate cutoff you need.

Check yourself

1. Why does the chance that two minimums match equal the Jaccard similarity? The smallest element of the combined set is equally likely to be any element of the union. The minimums match only when that element is in both sets.
2. Two documents have similarity 0.8. About how likely are they to be a candidate pair under 32 bands of 4? Almost certainly, about 1.00, since 1 − (1 − 0.4096)^32 is very close to 1.

Key takeaways

• Jaccard similarity measures overlap between sets. MinHash estimates it from random minimums.
• A 128-number signature estimates similarity with an error of about 0.09 and fits in 512 bytes.
• LSH banding finds similar pairs by hashing signature bands. Only pairs that collide in some band are compared.
• The same idea, applied to vectors, underlies approximate nearest-neighbor search.

Further learning

Embeddings are the usual input to vector search. For how similar vectors are stored and found, see vector databases and embeddings.