Вероятни структури от данни: Каква е разликата между филтрите MinHash и Bloom?


Отговор 1:

MinHash се използва предимно за бърза и точна оценка на приликата на Жакард между две неща (например два документа, два комплекта ...).

Филтърът Bloom е ефективна структура от данни, която ви позволява бързо да подрязвате елементи, които не са част от даден набор, с възможността да не успее да изреже всички тях.

И двете имат вероятностен характер, но целта е много различна.

MinHash е много известен и много често се използва при извличане на информация.


Отговор 2:

Основният недостатък на филтрите за цъфтеж за търсене на сходство е, че те се насищат, когато се напълнят, така че ако вашите комплекти могат да имат много различни размери, ще получите лоши оценки на приликата за големите.

Поредицата от minhashes обаче не се насища, но разстоянието между две хеша последователности винаги остава безпристрастна оценка на приликата на Жакард.

Често обаче minhashe не се използват за създаване на скици. Основен случай за тях е създаването на ключове, които да се използват за клъстериране с ключ за съхранение на стойности и това е нещо, което не можете да направите с филтър за разцвет, освен ако не се занимавате само с съвпадения, които са много близки до точните. Можете да прочетете повече за това тук: MinHashing