MinHash Permutation Resemblance
Link minimum permutation ranks to exact set resemblance and finite signature collisions.
By Riano · Published · Updated · Report a correction
MinHash Permutation Resemblance
MinHash uses random permutations to estimate the Jaccard similarity of two sets. A single minimum rank across a uniform random permutation has the exact same probability of colliding as the ratio of elements in the intersection to the elements in the union.
Worked example: Sets overlap with 3 permutations
Let the universe be elements {0, 1, 2, 3, 4, 5}. Suppose Set A contains {0, 1, 3} and Set B contains {1, 2, 3}. We use 3 fixed permutations to compute the signature of each set.
- The intersection is {1, 3} (size 2) and the union is {0, 1, 2, 3} (size 4). The exact Jaccard similarity is 2/4 = 0.5.
- Permutation 1 is [0, 1, 2, 3, 4, 5]. The minimum rank for A is 0 (element 0). The minimum rank for B is 1 (element 1).
- Permutation 2 is [5, 4, 3, 2, 1, 0]. The minimum rank for A is 2 (element 3). The minimum rank for B is 2 (element 3).
- Permutation 3 is [2, 3, 4, 5, 0, 1]. The minimum rank for A is 1 (element 3). The minimum rank for B is 0 (element 2).
The signatures are A: "0, 2, 1" and B: "1, 2, 0". They collide on the second permutation (rank 2). Thus, 1 out of 3 signatures match, giving a signature collision fraction of 1/3 (≈0.3333333333333333).
Experiment with permutations
You can test different configurations using the MinHash Permutation Resemblance experiment.
- Set the Sets control to Disjoint. Notice that Set A and B share no elements, so Jaccard similarity is 0 and there are no signature collisions.
- Change Permutations to 6. More permutations generally improve the signature collision fraction as an estimator for the Jaccard similarity, although deterministic fixed tables do not provide unbiased randomness guarantees.
Limitations and fixed sets
This demonstration uses a very small, fixed set of exactly 6 permutations rather than true uniform random permutations.
Because the permutations are deterministic, the signature collision fraction is not an unbiased estimator or a confidence guarantee of the true similarity. Additionally, empty sets require a special sentinel value (rank 6) to allow computation, and an empty/empty comparison yields a similarity of 1 by convention.
References
The original formulation of using min-wise independent permutations to estimate resemblance was introduced by Andrei Broder:
- On the resemblance and containment of documents by Andrei Z. Broder (1997).
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive MinHash Permutation Resemblance module.
Try MinHash Permutation Resemblance on Riano →