MinHash
MinHash is the set-similarity estimation method proposed by Broder: the minimum values of several independent hash functions are used to estimate the Jaccard similarity.
Purpose
It quickly estimates the Jaccard similarity between two sets among massive collections, supporting near-duplicate search and deduplication.
Mechanism
Apply k independent hash functions to the set and take each minimum, forming a k-dimensional signature. The probability that corresponding signature positions are equal equals the Jaccard similarity, so the fraction of matching positions estimates the similarity.
Use cases
- Near-duplicate detection in search engines
- Similar-item recommendation
- Document clustering