MinHashing vs SimHashing

Предположим, у меня есть пять наборов, которые я бы хотел сгруппировать. Я понимаю, что техника SimHashing описана здесь:

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

может привести к трем кластерам ( {A}, {B,C,D}и {E}), например, если его результаты были:

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

Точно так же метод MinHashing описан в главе 3 книги MMDS:

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

может также дать те же три кластера, если его результаты были:

A -> h01 - h02 - h03

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

E -> h11 - h12 - h13

(Каждый набор соответствует сигнатуре MH, состоящей из трех «полос», и два набора группируются, если хотя бы одна из их полос подписи совпадает. Чем больше полос, тем больше шансов на совпадение.)

Однако у меня есть несколько вопросов, связанных с этим:

(1) Можно ли понимать SH как однополосную версию MH?

(2) Обязательно ли MH подразумевает использование структуры данных, такой как Union-Find, для построения кластеров?

(3) Прав ли я, полагая, что кластеры в обоих методах на самом деле являются «предкластерами» в том смысле, что они являются просто наборами «пар-кандидатов»?

$O(n^2)$

Как правильно указано выше, MinHash и SimHash оба относятся к Locality Sensitive Hashing. Ссылка: https://en.wikipedia.org/wiki/Locality-sensitive_hashing

Основное различие между ними заключается в способе обработки столкновения,

1. SimHash, использует косинусное сходство
2. MinHash, использует Jaccard Index.

Ответы на ваши вопросы:

1. Нет. Они используют разные методы обработки столкновений для проверки сходства. Также есть вариант для одной хэш-функции для минимального хэша, но он работает по-другому. Для получения более подробной информации, проверьте следующую ссылку, https://en.wikipedia.org/wiki/MinHash (вариант с одной хэш-функцией)
2. Да, https://github.com/chrisjmccormick/MinHash/blob/master/runMinHashExample.py
3. $O(n \log n)$