MinHash
MinHash ist das von Broder vorgeschlagene Verfahren zur Schätzung von Mengenähnlichkeit: Die Minima mehrerer unabhängiger Hashfunktionen schätzen die Jaccard-Ähnlichkeit.
Zweck
Schätzt schnell die Jaccard-Ähnlichkeit zweier Mengen in massiven Sammlungen und unterstützt Near-Duplicate-Suche und Deduplizierung.
Mechanismus
Auf die Menge werden k unabhängige Hashfunktionen angewandt und jeweils das Minimum genommen, was eine k-dimensionale Signatur ergibt. Die Wahrscheinlichkeit, dass entsprechende Signaturpositionen gleich sind, entspricht der Jaccard-Ähnlichkeit; der Anteil übereinstimmender Positionen schätzt daher die Ähnlichkeit.
Anwendungsfälle
- Near-Duplicate-Erkennung in Suchmaschinen
- Ähnlichkeitsbasierte Empfehlungen
- Dokument-Clustering