MinHash › Worked Example

Let's walk through a concrete MinHash computation with a small example that you can follow step by step. This will solidify both the mechanics of the algorithm and the intuition behind why it works.

Suppose we have two documents:

• Document A: "data science is great"
• Document B: "data science is wonderful"

We extract 2-word shingles:

• A's shingles: {data science, science is, is great}
• B's shingles: {data science, science is, is wonderful}

The intersection is {data science, science is}, with 2 elements. The union has 4 distinct shingles: {data science, science is, is great, is wonderful}. So the exact Jaccard similarity is:

$$J(A, B) = \frac{2}{4} = 0.5$$

Now suppose we assign integer IDs to the 4 distinct shingles: data science = 0, science is = 1, is great = 2, is wonderful = 3. We use two hash functions:

$$h_1(x) = (3x + 1) \bmod 5$$ $$h_2(x) = (x + 2) \bmod 5$$

Computing hash values for each shingle ID:

• $h_1(0) = 1$, $h_1(1) = 4$, $h_1(2) = 2$, $h_1(3) = 0$
• $h_2(0) = 2$, $h_2(1) = 3$, $h_2(2) = 4$, $h_2(3) = 0$

Document A contains shingle IDs $\{0, 1, 2\}$, so its MinHash signature is:

$$\text{sig}(A) = \left[\min(h_1(0), h_1(1), h_1(2)),\; \min(h_2(0), h_2(1), h_2(2))\right]$$ $$= \left[\min(1, 4, 2),\; \min(2, 3, 4)\right] = [1, 2]$$

Document B contains shingle IDs $\{0, 1, 3\}$, so its MinHash signature is:

$$\text{sig}(B) = \left[\min(h_1(0), h_1(1), h_1(3)),\; \min(h_2(0), h_2(1), h_2(3))\right]$$ $$= \left[\min(1, 4, 0),\; \min(2, 3, 0)\right] = [0, 0]$$

The estimated Jaccard similarity is the fraction of positions where the signatures agree:

$$\hat{J}(A, B) = \frac{0}{2} = 0$$

Both positions disagree, giving an estimate of 0. The true Jaccard is 0.5. This is a bad estimate, but that's expected: with only 2 hash functions, variance is enormous. The standard deviation at $J = 0.5$ with $k = 2$ is $\sqrt{0.25 / 2} \approx 0.35$, so getting an estimate anywhere from 0 to 1 is quite plausible.

With $k = 128$ hash functions, the standard deviation would be $\sqrt{0.25 / 128} \approx 0.044$, and the estimate would almost certainly fall close to 0.5. This variance reduction is why practical MinHash implementations use 128 to 256 hash functions.