MinHash
MinHash est la méthode d'estimation de similarité d'ensembles proposée par Broder : les valeurs minimales de plusieurs fonctions de hachage indépendantes servent à estimer la similarité de Jaccard.
Objectif
Estime rapidement la similarité de Jaccard entre deux ensembles au sein de collections massives, soutenant la recherche de quasi-dupliqués et la déduplication.
Mécanisme
On applique k fonctions de hachage indépendantes à l'ensemble et on prend chaque minimum, formant une signature à k dimensions. La probabilité que les positions correspondantes de la signature soient égales vaut la similarité de Jaccard ; la fraction de positions concordantes estime donc la similarité.
Cas d’usage
- Détection de quasi-dupliqués dans les moteurs de recherche
- Recommandation d'éléments similaires
- Clustering de documents