MinHash

MinHash is a way to estimate how similar two sets are by comparing short fixed-length summaries (signatures) instead of the sets themselves. It exists because near-duplicate detection compares documents by the overlap of their word sequences, and comparing every pair of documents in a large dataset is quadratic in the number of documents. With MinHash each document is reduced once to a signature of a few hundred integers, and similarity is read off by counting how many positions of two signatures agree.

The quantity being estimated

Turn each text into a set of shingles, the overlapping runs of \(k\) words (here \(k=3\)). The Jaccard similarity of two sets \(A\) and \(B\) is

\[ J(A,B)=\frac{|A\cap B|}{|A\cup B|}, \]

the share of all shingles that appear in both. It is 1 for identical sets and 0 for disjoint ones. Computing it exactly needs both sets; MinHash approximates it from signatures.

How a signature is built

Take a hash function \(h\) that maps every possible shingle to a number, and treat the hash values as a random ordering of all shingles. For a set \(S\), define \(\min h(S)\) as the smallest hash value among its shingles.

Now look at the union \(A\cup B\). Because the ordering is random, each element of the union is equally likely to be the one with the smallest hash. The two sets have the same minimum exactly when that element belongs to both, that is, when it lies in \(A\cap B\). Therefore

\[ \Pr[\min h(A)=\min h(B)] = \frac{|A\cap B|}{|A\cup B|}=J(A,B). \]

One hash function gives one yes/no observation whose success probability is the Jaccard similarity. A signature uses \(n\) independent hash functions, and the estimate is the fraction of the \(n\) positions where the two signatures are equal. This is an average of \(n\) independent Bernoulli trials, so it is unbiased and its standard error is \(\sqrt{J(1-J)/n}\). The error depends on \(n\) and not on the size of the documents: a 64-position signature describes a tweet and a book equally precisely.

Worked example

Take a hypothetical support message, “please reset my account password because the recovery link expired before I could use it today”, and a second message that adds “hello” to its front. Lowercase the text and use whitespace-separated three-word shingles. The first has 14 distinct shingles, the second has 15, and 14 are shared, so \(J = 14/15 = 0.933\). This standard-library Python example hashes each shingle with MD5 salted by a run number and hash-function index. It first compares signature estimates with the ideal independent-ordering standard error, then repeats the check on two sets of 60 elements with 30 shared:

import hashlib
import statistics as st

message = "please reset my account password because the recovery link expired before I could use it today"

def shingles(text, size=3):
    words = text.lower().split()
    return {" ".join(words[i:i+size]) for i in range(len(words)-size+1)}

def signature(items, length, run=0):
    return [min(int.from_bytes(hashlib.md5(f"{run}:{i}:{x}".encode()).digest(), "big")
                for x in items) for i in range(length)]

def estimate(a, b, length, run=0):
    sa, sb = signature(a, length, run), signature(b, length, run)
    return sum(x == y for x, y in zip(sa, sb)) / length

A, B = shingles(message), shingles("hello " + message)
J = len(A & B) / len(A | B)
print("shingles:", len(A), len(B), "shared", len(A & B), "J", round(J, 3))
for n in (16, 64, 256, 1024):
    print(n, f"{estimate(A, B, n):.3f}", f"{(J*(1-J)/n)**0.5:.3f}")

A, B = {str(i) for i in range(60)}, {str(i) for i in range(30, 90)}
J = len(A & B) / len(A | B)
print("second J", round(J, 6))
for n in (16, 64, 256):
    values = [estimate(A, B, n, run) for run in range(200)]
    print(n, f"{st.stdev(values):.3f}", f"{(J*(1-J)/n)**0.5:.3f}")

signature length \(n\)	estimate	ideal standard error
16	1.000	0.062
64	0.953	0.031
256	0.957	0.016
1024	0.920	0.008

The second check has \(J=30/(60+60-30)=1/3\). Over 200 repeated signatures, the sample standard deviations are 0.126, 0.064 and 0.028 for \(n=16,64,256\), compared with ideal standard errors 0.118, 0.059 and 0.029. The run number changes the salt between repetitions. MD5 supplies a practical deterministic approximation to independent random orderings, so the finite-run sample deviations need not equal the ideal formula. Because ideal error shrinks as \(1/\sqrt n\), going from 64 to 256 positions halves it, and a stricter threshold needs a longer signature.

Avoiding the all-pairs comparison

Signatures make each comparison cheap, but comparing all pairs is still quadratic in the number of documents. Locality-sensitive hashing (LSH) avoids it by generating only a sparse set of candidate pairs, so most pairs are never compared in full. Cut each signature into \(b\) bands of \(r\) positions; two documents become a candidate pair if they agree on all \(r\) positions in at least one band. For a pair with true similarity \(s\), a band matches with probability \(s^r\), so the pair becomes a candidate with probability

\[ 1-(1-s^r)^b . \]

With \(b=20\), \(r=5\) (a 100-position signature), this curve is steep around \(s\approx(1/b)^{1/r}=0.55\): pairs at \(s=0.2\) become candidates 0.6% of the time, at \(0.4\) 18.6%, at \(0.6\) 80.2%, and at \(0.8\) 99.96%. Only candidates are then checked, with the exact Jaccard similarity or the full signature. If many documents fall into the same bucket, the number of candidate pairs can itself grow quadratically, so the saving depends on the candidates staying sparse. The band count and width are chosen so that the steep part of the curve sits at the similarity threshold you care about.

What it detects and what it does not

• MinHash estimates set overlap. Reordering a text can break shingles even when it keeps every word; moving “because the recovery link expired before I could use it today” to the front of the example message leaves 12 shared three-word shingles in a union of 16, so Jaccard falls to 0.750. Single-word shingles still give 1.0 because every word remains present. The shingle length therefore sets what counts as similar: longer shingles are more specific and miss reorderings, shorter ones catch more rewrites but flag unrelated texts that share vocabulary.
• It cannot see paraphrases that share few exact word sequences. Embedding similarity covers that case at the cost of false positives.
• It treats sets, so repeated shingles within a document are ignored. Weighted variants exist, but the basic method does not use counts.
• It is probabilistic: a pair near the threshold can be missed, and the miss rate is what the banding curve above quantifies.

MinHash is a means of finding near-duplicates between training and evaluation data, or within a corpus; deciding which side to drop and what threshold to use are separate choices that depend on the task.

References

• Broder, "On the resemblance and containment of documents" (1997), the original description of shingling and min-wise hashing.
• Leskovec, Rajaraman, Ullman, Mining of Massive Datasets, chapter 3 (Finding Similar Items)