MinHash and LSH Visualization | Jaccard, Signatures, LSH Bands

The idea: similar sets share min hashes

Finding near-duplicate documents among millions means comparing sets of words. Comparing every pair costs n²/2 comparisons, and each set can be large. MinHash shrinks every set to a short signature of k numbers, and locality-sensitive hashing (LSH) puts similar signatures in the same bucket, so only those pairs are checked.

Four documents A, B, C and D become columns of a 6-row signature matrix. The rows are cut into 3 bands of 2 rows. In bands 1 and 3, A and B have the same values, so they land in the same bucket and become a candidate pair; C and D are alone in their buckets — Sets become 6-number signatures; bands of 2 rows are hashed to buckets, and only A and B meet in a bucket.

The page has four documents, each a set of words with ids 0 to 12. Press MinHash to build a signature, Compare to estimate the similarity of two documents, and Find Candidates to run LSH with the banding in the bands menu.

Jaccard similarity

The Jaccard similarity of two sets is J(A, B) = |A ∩ B| / |A ∪ B|: shared words over all distinct words. A = {the, cat, sat, on, mat, today} and B = {the, cat, sat, on, a, mat} share 5 of 7 words, so J = 0.71. Documents are often turned into sets of shingles (every run of k words or characters); this page uses single words to keep the sets small.

pair	shared / all	J
A–B	5 / 7	0.71
B–C	4 / 8	0.50
A–C	3 / 9	0.33
A–D, B–D, C–D	1 / 10	0.10

MinHash signatures

Pick a hash function h that orders the words at random. The MinHash of a set is the smallest h(x) over its words. Do this with k different hashes and you get a signature of k numbers. The page uses k = 6 hashes h_i(x) = (a_i·x + b_i) mod 17; because 17 is a prime above the 13 word ids, each one is a permutation of the ids and there are no ties (Demo 1).

A signature has 6 numbers however many words the document has, and it can be built in one pass over the words.

Why P(same min) = J

Look at the union A ∪ B under a random order. The smallest word of the union is equally likely to be any of its |A ∪ B| words. Both sets have the same min exactly when that word is in both, which happens for |A ∩ B| of them. So P[min h(A) = min h(B)] = J(A, B).

The share of the k rows where two signatures agree is therefore an unbiased estimate Ĵ of J, with a standard error of about √(J(1 − J)/k). A and B agree in 5 of 6 rows: Ĵ = 0.83 for a true 0.71 (Demo 2). A and C agree in 2 rows, exactly J = 0.33, and A and D in 1 row, 0.17 for a true 0.10 (Demo 3). Real systems use 128 or 256 hashes, which brings the error near 0.03.

LSH banding

Signatures are small, but comparing all pairs is still n²/2 work. Banding avoids it: cut the k rows into b bands of r rows (b·r = k). For each band, hash its r values to a bucket. Two documents with the same values in every row of some band land in the same bucket and become a candidate pair. Only candidates are compared in full.

For a pair with similarity J, one band matches with probability J^r, so

P (candidate) = 1 - {(1 - J^{r})}^{b}

This is an S-curve: low for dissimilar pairs, high for similar ones, with the steep part near the threshold t ≈ (1/b)^1/r.

More bands catch more pairs (false positives); longer bands catch fewer (false negatives).

Choosing b and r

b × r	threshold	candidates here	result
6 × 1	0.17	A–B, A–C, A–D, B–C	3 false positives (Demo 5)
3 × 2	0.58	A–B (bands 1 and 3)	exact (Demo 4)
2 × 3	0.79	A–B	exact, by luck
1 × 6	1.00	none	A–B missed (Demo 6)

Pick the threshold near the similarity you care about. A false positive only costs one extra full comparison, which removes it. A false negative is a near duplicate you never see, so systems usually set the threshold a little below the target and raise k to make the S steeper.

Real uses

Web and corpus dedup: Broder built MinHash at AltaVista to find near-duplicate web pages; LLM training sets are deduplicated with MinHash LSH over 5-gram shingles.
Libraries: Python datasketch (MinHash, MinHashLSH(threshold=0.5, num_perm=128)) and Spark ML MinHashLSH with approxSimilarityJoin.
Other set-like data: similar users from the items they bought, plagiarism checks, and genome comparison (Mash).

MinHash is one of the sketches next to the Bloom Filter (membership), the Count-Min Sketch (frequency) and HyperLogLog (distinct count): a fixed number of hashed values that summarise a set.

What the page leaves out

Shingling and normalisation of real text; 128–256 fast hashes or one hash with k permutations (one-permutation hashing, b-bit MinHash); weighted MinHash for multisets; SimHash and random-hyperplane LSH for cosine similarity; multi-probe LSH and LSH forest; and the step that turns candidate pairs into clusters of duplicates.

See where this page fits on the Indexing mind map.