Was vorteilhafter Minhash über Simhash?

Question

Ich arbeite mit Simhash, aber auch Minhash ist effektiver.
Aber ich verstehe es nicht.
Bitte erklären Sie mir: Was vorteilhafter Minhash über Simhash?

Answer 1

In Simhash müssen wir keine Hyperebenen speichern. Es hat etwas schlechtere Fehlergrenzen. Simhash lecture

Answer 2

Simhash ist schneller und benötigt in der Regel kleinere Speicheranforderungen als Minhash, ist jedoch dadurch eingeschränkt, dass es nur sehr ähnliche Ähnlichkeiten erkennen kann. Wenn zwei Elemente mehr als eine kleine Menge unterscheiden, wird ihre Ähnlichkeit nicht erkannt. Minhash hingegen kann verwendet werden, um auch ziemlich entfernte Ähnlichkeiten zu erkennen, wie zum Beispiel Gegenstände, die nur 5% Ähnlichkeit zueinander haben. Simhash ist auch ein wenig komplexer zu verstehen.

Minhash beruht auf der Erzeugung mehrerer Hashes pro Element, z. in der Regel irgendwo zwischen 20 und 400 64-Bit-Hashes. Diese Hashes müssen zusammen mit der ID des Elements, zu dem sie gehören, zusammen mit dem Hash-Index gespeichert werden. Um alle Artikel zu finden, die z.B. 50% geschätzte Ähnlichkeit mit einem bestimmten Gegenstand, Sie müssen alle anderen Gegenstände finden, die mindestens 50% der Hashes des gegebenen Gegenstandes teilen. Dies kann das Aufzählen einer ziemlich großen Anzahl von hash-itemID-Paaren beinhalten.

Simhash andererseits verwendet nur einen einzelnen Hash pro Element, z. ein 64-Bit-Hash; und dieser Hash wird so erzeugt, dass sehr ähnliche Items Hashes mit sehr ähnlichen Bitmustern haben. Dieser Hash muss (zusammen mit der ID des Elements) in mehreren Tabellen (z. B. 8 verschiedenen Tabellen) gespeichert werden, wobei jede Tabelle die Bits des Hash auf verschiedene Arten permutiert und jede Tabelle die permutierten Hashes in numerischer Reihenfolge sortiert. Die Verwendung mehrerer Tabellen ermöglicht einen cleveren Trick, mit dem Sie schnell alle Hashes finden können, die sich um höchstens n Bits von einem gegebenen Hash unterscheiden; das Problem ist, dass n nicht groß sein kann: abhängig davon, wie viele Elemente Sie erwarten, zu speichern, wie viele Bits im gesamten Hash und wie viele Tabellen Sie im Speicher halten können, n möglicherweise so niedrig wie 3 oder möglicherweise so hoch wie 6 oder 7.

Minhash und Simhash beide hängen für ihre Geschwindigkeit auf ihre Tabellen im Hauptspeicher gehalten, obwohl beide über mehrere Maschinen aufgeteilt werden können, wenn Sie Speicher Einschränkungen überwinden müssen. Die Methode, einen Simhash zu erstellen, wird durch ein Patent von Google abgedeckt, obwohl sie zumindest den nichtkommerziellen Gebrauch des Algorithmus zu erlauben scheinen.