AltaVista trouvait les pages quasi dupliquées en esquissant leur ressemblance de Jaccard

L'index d'un moteur de recherche regorge de pages mises en miroir et copiées, et les dédupliquer naïvement implique de comparer chaque page à toutes les autres — des millions au carré.

Les travaux de Broder en 1997 représentaient une page comme un ensemble de shingles, puis n'en conservaient qu'une poignée ayant le plus petit hachage sous une permutation. Les ensembles de deux pages partagent une valeur minimale proportionnellement à leur ressemblance de Jaccard, si bien qu'une courte esquisse estime la similarité sans aucune comparaison par paires.

AltaVista utilisait l'esquisse pour regrouper les pages quasi dupliquées du web et écarter les copies des résultats. La méthode transformait un problème de similarité insoluble en une simple opération de hachage rapide.

Des hachages minimaux identiques signifient que les pages se ressemblent

Quelques hachages minimaux estiment la similarité de Jaccard sans comparaison élément par élément.

La signature est de taille fixe, si bien que le coût par page est minime et qu'elle se stocke bien.

C'est un estimateur sans biais, correct en moyenne sur l'ensemble des pages.

La même esquisse permet la détection de quasi-doublons et le regroupement à grande échelle.

Ne comparez pas deux grands ensembles élément par élément. Réduisez chacun à quelques hachages minimaux, de sorte que la probabilité qu'ils concordent égale le recouvrement des ensembles, et le problème devient minuscule.

MinHash est devenu un fondement de la détection de quasi-doublons à grande échelle, de la similarité d'ensembles et de la déduplication dans la recherche, la publicité et l'apprentissage automatique, puis la famille du hachage sensible à la localité s'est construite dessus.