MinHashing vs SimHashing

Supongamos que tengo cinco conjuntos que me gustaría agrupar. Entiendo que la técnica SimHashing descrita aquí:

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

podría producir tres grupos ( {A}, {B,C,D}y {E}), por ejemplo, si sus resultados fueran:

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

Del mismo modo, la técnica MinHashing descrita en el Capítulo 3 del libro MMDS:

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

También podría producir los mismos tres grupos si sus resultados fueran:

A -> h01 - h02 - h03

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

E -> h11 - h12 - h13

(Cada conjunto corresponde a una firma MH compuesta de tres "bandas", y dos conjuntos se agrupan si al menos una de sus bandas de firma coincide. Más bandas significarían más posibilidades de coincidencia).

Sin embargo, tengo varias preguntas relacionadas con estos:

(1) ¿Se puede entender SH como una versión de banda única de MH?

(2) ¿MH implica necesariamente el uso de una estructura de datos como Union-Find para construir los clústeres?

(3) ¿Estoy en lo cierto al pensar que los grupos, en ambas técnicas, son en realidad "pre-grupos", en el sentido de que son solo conjuntos de "pares candidatos"?

(4) Si (3) es verdadero, ¿implica que todavía tengo que hacer una búsqueda dentro de cada "pre-cluster", para dividirlos en grupos "reales"? (lo que podría ser razonable si tengo muchos pre-grupos pequeños y bastante equilibrados, de lo contrario no tanto)$O(n^2)$

Como se señaló correctamente anteriormente, MinHash y SimHash pertenecen a Hashing sensible a la localidad. Referencia: https://en.wikipedia.org/wiki/Locality-sensitive_hashing

La principal diferencia entre los dos es la forma en que se maneja la colisión,

1. SimHash, usa similitud de coseno
2. MinHash, utiliza el índice Jaccard.

Respuestas a sus preguntas:

1. No. Usan diferentes técnicas de manejo de colisiones para validar la similitud. También hay una variante en la función Hash simple para Min Hash pero funciona de manera diferente. Para obtener más detalles, consulte la siguiente referencia, https://en.wikipedia.org/wiki/MinHash (Variante con una sola función hash)
2. Sí, https://github.com/chrisjmccormick/MinHash/blob/master/runMinHashExample.py
3. Creo que la complejidad se puede reducir a con una forma modificada de búsqueda binaria mientras se agrupa.$O(n \log n)$