MinHashing vs SimHashing

Suponha que eu tenha cinco conjuntos que gostaria de agrupar. Entendo que a técnica SimHashing descrita aqui:

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

poderia gerar três clusters ( {A}, {B,C,D}e {E}), por exemplo, se seus resultados fossem:

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

Da mesma forma, a técnica MinHashing descrita no Capítulo 3 do livro MMDS:

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

também poderia gerar os mesmos três clusters se seus resultados fossem:

A -> h01 - h02 - h03

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

E -> h11 - h12 - h13

(Cada conjunto corresponde a uma assinatura MH composta por três "bandas" e dois conjuntos são agrupados se pelo menos uma de suas bandas de assinatura estiver combinando. Mais bandas significam mais chances de correspondência.)

No entanto, tenho várias perguntas relacionadas a estes:

(1) SH pode ser entendido como uma versão de banda única do MH?

(2) O MH implica necessariamente o uso de uma estrutura de dados como o Union-Find para criar os clusters?

(3) Estou certo ao pensar que os clusters, em ambas as técnicas, são realmente "pré-clusters", no sentido de que são apenas conjuntos de "pares candidatos"?

$O(n^2)$

Conforme corretamente indicado acima, o MinHash e o SimHash pertencem ao Hashing sensível à localidade. Referência: https://en.wikipedia.org/wiki/Locality-sensitive_hashing

A principal diferença entre os dois é a maneira como a colisão é tratada,

1. SimHash, usa semelhança de cosseno
2. MinHash, usa o índice Jaccard.

Respostas às suas perguntas:

1. Não. Eles usam diferentes técnicas de manipulação de colisões para validar a similaridade. Também existe uma variante da Função Hash única para Min Hash, mas funciona de maneira diferente. Para obter mais detalhes, consulte a seguinte referência, https://en.wikipedia.org/wiki/MinHash (variante com uma única função de hash)
2. Sim, https://github.com/chrisjmccormick/MinHash/blob/master/runMinHashExample.py
3. $O(n \log n)$