В настоящее время я изучаю, как найти ближайшего соседа, используя хеширование с учетом локальных особенностей. Однако пока я читаю статьи и ищу в Интернете, я нашел два алгоритма для этого:

1- Используйте L количество хеш-таблиц с L числом случайных функций LSH, таким образом увеличивая вероятность того, что два документа, которые похожи, получат одну и ту же подпись. Например, если два документа похожи на 80%, то с 80% вероятностью они получат одинаковую подпись от одной функции LSH. Однако, если мы используем несколько функций LSH, есть больше шансов получить одну и ту же подпись для документов от одной из функций LSH. Этот метод объясняется в википедии, и я надеюсь, что мое понимание верно:

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

2- Другой алгоритм использует метод из статьи (раздел 5), который называется: Методы оценки сходства из алгоритмов округления Моисея С. Чарикара. Он основан на использовании одной функции LSH для генерации подписи, а затем применения к ней перестановок P и сортировки списка. На самом деле я не очень хорошо понимаю этот метод и надеюсь, что кто-нибудь сможет уточнить его.

Мой главный вопрос: зачем кому-то использовать второй метод, а не первый? Как я считаю, это проще и быстрее.

Я действительно надеюсь, что кто-то может помочь !!!

РЕДАКТИРОВАТЬ: На самом деле я не уверен, что @ Raff. Эдвард смешивал между «первым» и «вторым». Потому что только во втором методе используется радиус, а в первом - новое хеш-семейство g, состоящее из хеш-семейства F. Пожалуйста, проверьте ссылку в Википедии. Они просто использовали много g-функций для генерации разных сигнатур, а затем для каждой g-функции имеется соответствующая хеш-таблица. Чтобы найти ближайшего соседа точки, просто дайте точке пройти через g-функции и проверьте соответствующие хеш-таблицы на наличие коллизий. Таким образом, как я понял это как больше функции ... больше шансов для столкновений.

Я не нашел упоминания о радиусе для первого метода.

Для второго метода они генерируют только одну сигнатуру для каждого вектора признаков и затем применяют к ним P-перестановки. Теперь у нас есть P списков перестановок, каждая из которых содержит n подписей. Затем они сортируют каждый список из P. После этого, имея заданную точку запроса q, они генерируют для нее сигнатуру и затем применяют к ней перестановки P, а затем используют бинарный поиск в каждом переставленном и отсортированном P-списке, чтобы найти наиболее похожую сигнатуру для запрос q. Я пришел к выводу, прочитав много статей об этом, но я до сих пор не понимаю, зачем кому-то использовать такой метод, потому что кажется, что он не быстро находит расстояние Хэмминга !!!!

Для меня я бы просто сделал следующее, чтобы найти ближайшего соседа для точки запроса q. Учитывая список сигнатур N, я сгенерирую сигнатуру для точки запроса q, а затем отсканирую список N и вычислю расстояние Хемминга между каждым элементом в N и сигнатурой q. Таким образом, я бы в конечном итоге с ближайшим соседом для q. И это занимает O (N) !!!