MinHashing vs SimHashing

Załóżmy, że mam pięć zestawów, które chciałbym połączyć. Rozumiem, że opisana tutaj technika SimHashing:

https://moultano.wordpress.com/2010/01/21/simple-simhashing-3kbzhsxyg4467-6/

może przynieść trzy klastry ( {A}, {B,C,D}i {E}), na przykład, gdy jego wyniki:

A -> h01
B -> h02
C -> h02
D -> h02
E -> h03

Podobnie technika MinHashing opisana w rozdziale 3 książki MMDS:

http://infolab.stanford.edu/~ullman/mmds/ch3.pdf

mógłby również dać te same trzy klastry, gdyby jego wyniki były następujące:

A -> h01 - h02 - h03

B -> h04 - h05 - h06
      |
C -> h04 - h07 - h08
                  |
D -> h09 - h10 - h08

E -> h11 - h12 - h13

(Każdy zestaw odpowiada sygnaturze MH złożonej z trzech „pasm”, a dwa zestawy są zgrupowane, jeśli co najmniej jeden z ich pasm sygnatury jest zgodny. Więcej pasm oznaczałoby więcej szans na dopasowanie.)

Mam jednak kilka pytań z tym związanych:

(1) Czy SH można rozumieć jako jednopasmową wersję MH?

(2) Czy MH niekoniecznie oznacza użycie struktury danych takiej jak Union-Find do budowy klastrów?

(3) Czy mam rację, sądząc, że klastry w obu technikach są tak naprawdę „klastrami wstępnymi”, w tym sensie, że są tylko zestawami „par kandydujących”?

$O(n^2)$

Jak prawidłowo wskazano powyżej, MinHash i SimHash należą do funkcji mieszania wrażliwego na lokalizację. Odniesienie: https://en.wikipedia.org/wiki/Locality-sensitive_hashing

Główną różnicą między nimi jest sposób radzenia sobie z kolizją,

1. SimHash wykorzystuje podobieństwo cosinus
2. MinHash, wykorzystuje indeks Jaccard.

Odpowiedzi na twoje pytania:

1. Nie. Używają różnych technik obsługi kolizji, aby sprawdzić podobieństwo. Istnieje również wariant funkcji Single Hash dla Min Hash, ale działa inaczej. Aby uzyskać więcej informacji, sprawdź następujące odniesienie: https://en.wikipedia.org/wiki/MinHash (wariant z jedną funkcją skrótu)
2. Tak, https://github.com/chrisjmccormick/MinHash/blob/master/runMinHashExample.py
3. $O(n \log n)$