Similarity & High-Dimensional Search

MinHash

Estimate how similar two sets are from the chance their smallest hash collides — Jaccard similarity in a handful of numbers.

Top bar: the true overlap of A and B — green = shared, blue = A only, purple = B only (so J = the green fraction). Each column below is one hash: green if the two signatures match.

What you're seeing

The top bar is the ground truth: the union of sets A and B, split into the part they share (green) and the parts unique to each. The Jaccard similarity J = |A∩B| / |A∪B| is just the green fraction of that bar. Below, each column is one random hash function: it computes the smallest hash value in A and the smallest in B, and turns green when those agree. The fraction of green columns is the estimate — and as columns accumulate, that fraction homes in on the green fraction up top.

The rule

signature(S):  for each of m random hashes h:
                   sig[h] = min over x in S of h(x)
estimate J(A,B) = (# hashes where sig_A[h] == sig_B[h]) / m

Each set is reduced to a fixed-length signature of m numbers; comparing two sets is then just comparing two signatures, regardless of how big the sets were.

The guarantee

For a single random hash, P[ minhash(A) = minhash(B) ] = J(A,B). The argument is one sentence: consider the element of A∪B with the globally smallest hash value; under a random hash every element of the union is equally likely to be that minimizer, and the two signatures agree exactly when it happens to lie in A∩B — which has probability |A∩B|/|A∪B| = J. Each hash is therefore an unbiased coin-flip with bias J, so averaging m independent hashes gives an unbiased estimate of J with variance J(1−J)/m: relative error shrinks like 1/√m. Slide Hash functions up and watch the estimate tighten onto the true value — exactly what this entry's test checks across thousands of seeded hash families.

The cost

Build signatureCompare twoStore MinHashO(m·|S|)O(m)O(m) Exact Jaccard—O(|A|+|B|)O(|S|)

The win is that the signature size m is fixed and tiny — independent of how large the sets are. You can store an m-number fingerprint per document and compare any two in O(m), or bucket millions of them. More hashes buy more accuracy linearly in space; the variance, not the set size, sets the budget.

In the wild

MinHash (Andrei Broder, AltaVista, 1997) was invented to find near-duplicate web pages — represent each page as a set of shingles (overlapping word k-grams), and two pages are near-duplicates if their MinHash signatures mostly agree. It still powers duplicate detection in search indexing and crawl dedup, plagiarism and similarity tools, and clustering of documents/genomes. Crucially it composes with locality-sensitive hashing: band the signature into chunks and hash each band, so similar items collide in a bucket — turning all-pairs similarity into a near-linear scan. An honest caveat: the clean P[match]=J result needs min-wise independent (effectively fully random) hashes; the cheap linear hash (a·x+b) mod p is only 2-universal and visibly biases the estimate — production code uses better hash families (or the one-permutation / bottom-k variants) for exactly this reason.

Try this

Set Shared elements to its max (A = B) and every column is green — estimate 1.0, exact. Set it to 0 (disjoint) and they're never green — estimate 0. In between, raise Hash functions from a handful to a hundred and watch the estimate stop wobbling and settle on the true Jaccard.

References

  1. Broder, A. "On the resemblance and containment of documents." Proc. Compression and Complexity of Sequences (SEQUENCES), 1997. The original MinHash.
  2. Broder, Charikar, Frieze & Mitzenmacher. "Min-wise independent permutations." STOC, 1998 — why the hashes must be min-wise independent.
  3. Leskovec, Rajaraman & Ullman. Mining of Massive Datasets, 2nd ed., Ch. 3 (Finding Similar Items) — MinHash + LSH. mmds.org.
  4. Andoni, A. Advanced Algorithms (Columbia COMS 4995-8, 2021), Lectures 7–9 (dimension reduction & LSH). course materials.