Probabilistische Datenstrukturen: Was ist der Unterschied zwischen MinHash- und Bloom-Filtern?


Antwort 1:

MinHash wird hauptsächlich verwendet, um die Jaccard-Ähnlichkeit zwischen zwei Dingen schnell und genau abzuschätzen (z. B. zwei Dokumente, zwei Sätze ...).

Ein Bloom-Filter ist eine effiziente Datenstruktur, mit der Sie Elemente, die nicht Teil eines Satzes sind, schnell entfernen können, wobei möglicherweise nicht alle Elemente entfernt werden können.

Beide sind probabilistischer Natur, aber der Zweck ist sehr unterschiedlich.

MinHash ist sehr bekannt und wird sehr häufig beim Abrufen von Informationen verwendet.


Antwort 2:

Der Hauptnachteil von Bloom-Filtern für die Ähnlichkeitssuche besteht darin, dass sie gesättigt sind, wenn sie voll sind. Wenn Ihre Sets also sehr unterschiedliche Größen haben können, erhalten Sie schlechte Schätzungen der Ähnlichkeit für die großen.

Eine Folge von Minhashes ist jedoch nicht gesättigt. Der Hamming-Abstand zwischen zwei Minhash-Sequenzen bleibt immer eine unvoreingenommene Schätzung der Jaccard-Ähnlichkeit.

Oft werden Minhashes jedoch nicht verwendet, um Skizzen zu erstellen. Ein Hauptanwendungsfall für sie ist das Erstellen von Schlüsseln für das Clustering mit einem Schlüsselwertspeicher. Dies können Sie mit einem Bloom-Filter nur tun, wenn Sie sich nur mit Übereinstimmungen befassen, die sehr genau sind. Mehr dazu lesen Sie hier: MinHashing