Der Index einer Suchmaschine ist voll von gespiegelten und kopierten Seiten, und sie naiv zu deduplizieren bedeutet, jede Seite mit jeder anderen zu vergleichen — Millionen zum Quadrat.
Broders Arbeit von 1997 stellte eine Seite als Menge von Shingles dar und behielt dann nur die wenigen mit dem kleinsten Hash unter einer Permutation. Die Mengen zweier Seiten teilen einen Minimalwert im Verhältnis zu ihrer Jaccard-Ähnlichkeit, sodass eine kurze Skizze die Ähnlichkeit ohne paarweisen Vergleich schätzt.
AltaVista nutzte die Skizze, um die nahezu doppelten Seiten des Webs zu clustern und die Kopien aus den Ergebnissen zu entfernen. Die Methode verwandelte ein unlösbares Ähnlichkeitsproblem in eine schnelle Hashing-Aufgabe.
Gleiche kleine Hashes bedeuten, dass Seiten ähnlich sind
Einige wenige minimale Hashes schätzen die Jaccard-Ähnlichkeit ohne Element-für-Element-Vergleich.
Die Signatur hat eine feste Größe, sodass die Kosten pro Seite winzig sind und sie sich gut speichern lässt.
Sie ist ein unverzerrter Schätzer, im Durchschnitt über die Seiten korrekt.
Dieselbe Skizze unterstützt die Erkennung nahezu doppelter Seiten und das Clustern im großen Maßstab.
Vergleiche nicht zwei große Mengen Element für Element. Reduziere jede auf einige wenige minimale Hashes, sodass die Wahrscheinlichkeit, dass sie übereinstimmen, der Überlappung der Mengen entspricht, und das Problem winzig wird.
MinHash wurde zu einer Grundlage der Erkennung nahezu doppelter Seiten im großen Maßstab, der Mengenähnlichkeit und der Deduplizierung in Suche, Werbung und maschinellem Lernen und später der darauf aufbauenden Familie des locality-sensitive Hashing.
DEN BELEGEN FOLGEN
Die Quellen
- On the resemblance and containment of documents DEC Systems Research Center Technical Note 1997-015 · bitsavers.org
- MinHash Wikipedia · en.wikipedia.org