⌂ Lectures
← →/space · tap / swipe to advance · F fullscreen
CSE2525 · Data Mining · 2026–27

MinHashing & Locality-Sensitive Hashing

Finding similar items among millions — without comparing every pair.
A. Anand · study deck · after Mining of Massive Datasets, ch. 3
Part I

Finding similar items at scale

Two walls: sets are huge, and comparing all pairs is quadratic.
Recall the near-duplicate system

Fast filter → slow check, made real

Where we left off

For near-duplicates we wanted cheap candidate generation, then expensive exact verification — and to never materialise all n² distances.

MinHash + LSH is exactly how you build that fast filter for set / text similarity. This lecture fills in the “how”.

A similarity for sets

Jaccard similarity

J(A,B) = |A ∩ B| / |A ∪ B|
Example A = {1,2,3,4}, B = {3,4,5} → |A∩B| = 2, |A∪B| = 5, so J(A,B) = 0.4.
Jaccard is 1 for identical sets, 0 for disjoint sets — and it’s what MinHash will secretly preserve.
Turn documents into sets

Shingling: text → a set of k-shingles

k-shingle Any substring of length k that appears in the document. The document becomes the set of its shingles.
“the cat sat”  →  k=2 words → { “the cat”, “cat sat” }
Why we can’t just compute Jaccard

Two walls

Sets are huge

  • Each doc = thousands of shingles
  • Storing / intersecting them is costly

Pairs are quadratic

  • N docs → N(N−1)/2 pairs
  • 1M docs → 5·10¹¹ comparisons
MinHash attacks the first wall (compress the sets); LSH attacks the second (skip most pairs).
Question
A million documents means about 5·10¹¹ possible pairs. How could you find the highly similar pairs without ever comparing most of them?
Two obstacles: the sets are huge, and the pairs are quadratic.
Think — then → for the answer.
Part II

MinHashing

A short signature that secretly preserves Jaccard.
Sets as columns of a 0/1 matrix

The characteristic matrix

elementS₁S₂S₃S₄
a1001
b0010
c0101
d1011
e0010
Rows = universe elements, columns = sets. We never build this explicitly — it’s a way to think about MinHash.
One number per set per permutation

MinHash = first 1 under a shuffle

Definition Pick a random permutation π of the rows. The MinHash of set S is the first row (in π-order) where S has a 1:
hπ(S) = minx∈S π(x).
In practice we don’t shuffle — we apply k independent hash functions to the row indices and keep each column’s running minimum. One pass over the data.
Why MinHash works at all

P(h(A) = h(B)) = J(A, B)

The one equation to remember

Under a random permutation, the probability two sets get the same MinHash equals their Jaccard similarity.

Why: classify rows as both-1 (count X), one-1 (count Y), or both-0 (ignored). Scanning from the top, the first non-both-0 row is equally likely to be any of them. It’s a “match” iff it’s a both-1 row → P = X / (X + Y) = J(A,B).

Compress columns to short signatures

The signature matrix

hashS₁S₂S₃S₄
h₁1301
h₂0200
h₃1211
Each column is a set’s signature — just k numbers (here k=3; real systems use ~100). Estimate J(Sᵢ,Sⱼ) = fraction of rows where their signatures agree.
Signatures stand in for sets

Longer signature → better estimate

What we bought

Each of k rows agrees with probability J, independently → the fraction of agreeing rows is an unbiased estimate of Jaccard, with error shrinking like 1/√k.

A giant set is now k small integers. The first wall is gone — but we’d still compare all N² signature pairs. That’s what LSH fixes.

Part III

Locality-Sensitive Hashing

Hash signatures so similar ones collide — and only compare collisions.
Split the signature into bands

The banding trick

bandS₁S₂S₃S₄
band 1a7c2a7a7
band 2x1x1q9k3
band 3m4m4p8m4
Split the length-n signature into b bands of r rows (n = b·r). Hash each band to a bucket. Same band value → same bucket.
Collide once → worth checking

Candidate = share a bucket in ≥ 1 band

Rule Two sets are a candidate pair if their signatures are identical in at least one band. Above: S₁ & S₃ collide in band 1; S₁ & S₄ collide in bands 1 and 3; S₁ & S₂ collide in bands 2 and 3.
Only candidate pairs get the expensive exact check. Most of the N² pairs never collide and are never looked at.
Tune collisions with b and r

Probability a pair becomes a candidate

P(candidate) = 1 − (1 − sr)b
b = 20 bands · r = 5 rows · signature = 100

The S-curve and its threshold

t ≈ 0.55 0.5 Jaccard similarity s → P(cand)
The jump sits near t ≈ (1/b)1/r ≈ 0.55. Pairs above t almost always become candidates; pairs below almost never do. Choosing b and r chooses the threshold.
Steepness vs. placement

Trading false positives against false negatives

You want…Do thisCost
Threshold lowerfewer rows r / more bands bmore candidates → more false positives
Threshold highermore rows r / fewer bands brisk missing pairs → false negatives
Sharper cutofflonger signature (bigger b·r)more hashing work
False positives are cheap — the exact check removes them. False negatives are lost forever, so err toward a slightly lower threshold.
Part IV

The pipeline & where it’s used

Shingle → MinHash → LSH → verify.
End to end

The whole system on one line

Shingledocs → sets
→
MinHashsets → signatures
→
LSH bandssignatures → candidates
→
Verifyexact Jaccard
This is the recipe from the Distances lecture

Cheap candidate generation (LSH) → expensive exact check (Jaccard on the survivors). No N² anywhere.

The same filter, everywhere

Where MinHash + LSH show up

LSH generalises: different similarities (cosine, Euclidean) have their own locality-sensitive hash families.
Take away · and a transfer exercise

Summary

The message

MinHash shrinks huge sets to short signatures with P(equal) = Jaccard. LSH bands those signatures so only similar pairs collide, giving an S-curve threshold you tune with b and r.

Together they turn an N² similarity search into a fast-filter → slow-check pipeline that scales to millions.

Transfer: you must dedup 10M product descriptions at threshold ≈ 0.8. Pick a signature length and a (b, r) split — and say which error you’d rather make.