MinHash › The MinHash Algorithm

Computing exact Jaccard similarity for every document pair in a large corpus is infeasible. If you have $n$ documents, there are $O(n^2)$ pairs. For a corpus with 100 billion documents, you would need to compare roughly $5 \times 10^{21}$ pairs. Even if each comparison took just one nanosecond, completing all comparisons would take over 150,000 years. No hardware can do this.

MinHash offers an elegant probabilistic approximation. Rather than computing the full shingle sets and comparing them, you compute a compact signature for each document such that signature similarity approximates Jaccard similarity. The idea originates in a 1997 paper by Broder, and it is built on a beautiful probabilistic identity about random permutations.

Imagine all possible shingles arranged in some arbitrary order, a permutation of the shingle universe. For a given document, look at the shingles it contains, then find the first shingle in the permutation that appears in the document. This is the minimum element under that permutation, hence the name "MinHash."

The key insight is a clean probabilistic fact. If you draw a uniformly random permutation $\pi$ of the shingle universe and compute the minimum element for documents $A$ and $B$ separately, the probability that both minima are the same equals the Jaccard similarity:

$$P\left(\min_{\pi}(A) = \min_{\pi}(B)\right) = \frac{|A \cap B|}{|A \cup B|} = J(A, B)$$

The proof is elegant and worth understanding. Consider the union $A \cup B$, which is the set of all shingles appearing in either document. Under a random permutation $\pi$, exactly one shingle in $A \cup B$ lands in the minimum position, that is, appears first in $\pi$ among all shingles in the union. Call this element $e^*$.

There are two cases:

1. $e^*$ falls in $A \cap B$ (it appears in both documents). Then $\min_\pi(A) = e^*$ and $\min_\pi(B) = e^*$, so the minima agree.
2. $e^*$ falls in $A \setminus B$ or $B \setminus A$ (it appears in only one document). Then one minimum is $e^*$ and the other is some different element, so the minima disagree.

By symmetry of a uniformly random permutation, each element in $A \cup B$ is equally likely to be $e^*$. The fraction of elements in $A \cup B$ that also belong to $A \cap B$ is precisely $|A \cap B| / |A \cup B|$, which is the Jaccard similarity. Therefore:

$$P\left(\min_{\pi}(A) = \min_{\pi}(B)\right) = \frac{|A \cap B|}{|A \cup B|} = J(A, B)$$

This is a single-bit estimator: it tells you whether the minima match, but a single comparison gives a binary answer (match or no match) with no granularity. To build a useful estimator, you need many independent trials.

To estimate Jaccard similarity reliably, you generate $k$ independent random permutations $\pi_1, \pi_2, \ldots, \pi_k$ and compute $k$ minima per document. These $k$ values form the MinHash signature: a vector of $k$ integers. The fraction of positions where two signatures agree gives an estimate of Jaccard similarity:

$$\hat{J}(A, B) = \frac{1}{k} \sum_{i=1}^{k} \mathbf{1}\left[\min_{\pi_i}(A) = \min_{\pi_i}(B)\right]$$

where $\mathbf{1}[\cdot]$ is the indicator function, equal to 1 when the condition holds and 0 otherwise.

The variance of this estimator decreases with $k$ following the formula for a Bernoulli average:

$$\text{Var}\left(\hat{J}\right) = \frac{J(1-J)}{k}$$

With $k = 128$ hash functions, the standard deviation at $J = 0.5$ (the worst case) is $\sqrt{0.25 / 128} \approx 0.044$. With $k = 256$, it falls to roughly $0.031$. The tradeoff is memory: $k$ 32-bit hash values per document requires $4k$ bytes, so 128-hash signatures cost 512 bytes and 256-hash signatures cost 1024 bytes per document. For a billion documents, this is 512 GB and 1 TB respectively, manageable in a distributed system.

Generating $k$ actual random permutations over a large shingle universe is impractical in two ways. First, a permutation over a universe of $2^{32}$ elements requires $2^{32}$ integer entries, or 16 GB just to store one permutation. Second, applying the permutation to find the minimum requires scanning all elements.

Instead, you simulate permutations using random hash functions. For each of the $k$ "permutations," define a hash function $h_i$ that maps shingle integers to a range of integers. The minimum hash value of the document's shingles under $h_i$ approximates the minimum element under a random permutation $\pi_i$, provided the hash function distributes values approximately uniformly.

A classic approach from the universal hashing literature uses linear functions modulo a prime:

$$h_{a,b}(x) = ((a \cdot x + b) \bmod p) \bmod M$$

where:

• $x$: the integer-hashed shingle value
• $a$: a random integer drawn uniformly from $\{1, \ldots, p-1\}$
• $b$: a random integer drawn uniformly from $\{0, \ldots, p-1\}$
• $p$: a large prime number larger than $M$ (for example, the Mersenne prime $2^{31} - 1$)
• $M$: the size of the hash space (for example, $2^{32}$)

For each of the $k$ hash functions, you pick different $(a, b)$ pairs. The minimum over all shingles in the document under $h_{a,b}$ gives one component of the MinHash signature.

Modern implementations often use faster non-cryptographic hash functions like MurmurHash3 or xxHash with different seeds for each of the $k$ positions. The critical requirement is that the hash functions distribute values uniformly and independently, which both MurmurHash and xxHash achieve with high quality. In very large pipelines, a technique called "one permutation MinHash" (or densified one permutation MinHash) uses a single hash of the document into a partitioned range, computing one minimum per partition rather than $k$ separate hashes, which is significantly faster.

It may seem surprising that simply taking the minimum hash value encodes useful similarity information. The intuition is that under a hash function with uniform output distribution, the minimum hash value of a large set of shingles is essentially a random sample from the shingle distribution. If two documents share many shingles, there is a high chance that the shingle with the smallest hash value appears in both. If they share few shingles, the minimums are likely to come from their non-overlapping portions and will differ.

More precisely, the minimum hash value is a random representative of the shingle set. Two documents with high Jaccard similarity are likely to pick the same representative because their shingle sets are nearly the same. Two documents with low Jaccard similarity are likely to pick different representatives.