Obecnie studiuję, jak znaleźć najbliższego sąsiada za pomocą haszowania wrażliwego na lokalność. Jednak podczas czytania artykułów i przeszukiwania sieci znalazłem dwa algorytmy do tego celu:

1- Użyj L tablic mieszających z L liczbą losowych funkcji LSH, zwiększając tym samym szansę, że dwa dokumenty, które są podobne, otrzymają ten sam podpis. Na przykład, jeśli dwa dokumenty są w 80% podobne, to istnieje 80% szansa, że ​​otrzymają ten sam podpis z jednej funkcji LSH. Jeśli jednak korzystamy z wielu funkcji LSH, istnieje większa szansa na uzyskanie tego samego podpisu dla dokumentów z jednej z funkcji LSH. Ta metoda została wyjaśniona w wikipedii i mam nadzieję, że moje zrozumienie jest poprawne:

http://en.wikipedia.org/wiki/Locality-sensitive_hashing#LSH_algorithm_for_nearest_neighbor_search

2- Drugi algorytm wykorzystuje metodę z artykułu (sekcja 5) o nazwie: Techniki szacowania podobieństwa z algorytmów zaokrąglania autorstwa Mosesa S. Charikara. Opiera się na wykorzystaniu jednej funkcji LSH do wygenerowania podpisu, a następnie nałożeniu na niego permutacji P, a następnie posortowaniu listy. Właściwie nie rozumiem tej metody bardzo dobrze i mam nadzieję, że ktoś mógłby to wyjaśnić.

Moje główne pytanie brzmi: dlaczego ktoś miałby używać drugiej metody, a nie pierwszej metody? Jak uważam, jest to łatwiejsze i szybsze.

Naprawdę mam nadzieję, że ktoś może pomóc !!!

EDYCJA: Właściwie nie jestem pewien, czy @ Raff.Edward miksowało między „pierwszym” a „drugim”. Ponieważ tylko druga metoda używa promienia, a pierwsza używa tylko nowej rodziny mieszającej g składającej się z rodziny skrótów F. Sprawdź link wikipedii. Użyli po prostu wielu funkcji g do wygenerowania różnych sygnatur, a następnie dla każdej funkcji g mają odpowiednią tablicę mieszania. Aby znaleźć najbliższego sąsiada punktu, po prostu pozwól punktowi przejść przez funkcje g i sprawdź odpowiednie tabele mieszania dla kolizji. Tak więc zrozumiałem to jako większą funkcję ... większą szansę na kolizje.

Nie znalazłem żadnej wzmianki o promieniu dla pierwszej metody.

W drugiej metodzie generują tylko jedną sygnaturę dla każdego wektora cech, a następnie stosują na nich permutacje P. Teraz mamy listy P permutacji, gdzie każda zawiera n podpisów. Teraz sortują każdą listę z P. Po podaniu punktu zapytania q generują dla niego podpis, a następnie stosują na nim permutacje P, a następnie używają wyszukiwania binarnego na każdej permutowanej i posortowanej liście P, aby znaleźć najbardziej podobny podpis do zapytanie q. Doszedłem do wniosku po przeczytaniu wielu artykułów na ten temat, ale nadal nie rozumiem, dlaczego ktoś miałby stosować taką metodę, ponieważ nie wydaje się to szybkie w znalezieniu odległości Hamminga !!!!

Dla mnie po prostu wykonaj następujące czynności, aby znaleźć najbliższego sąsiada dla punktu zapytania q. Biorąc pod uwagę listę sygnatur N, wygenerowałbym podpis dla punktu zapytania q, a następnie zeskanował listę N i obliczył odległość Hamminga między każdym elementem w N a podpisem q. Tak więc skończyłbym z najbliższym sąsiadem na q. I zajmuje O (N) !!!