MinHash Permutation Resemblance
Link minimum permutation ranks to exact set resemblance and finite signature collisions.
Free theory articleLink minimum permutation ranks to exact set resemblance and finite signature collisions.
Concept & interpretation
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.
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.