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

1- Используйте L количество хеш-таблиц с L числом случайных функций LSH, таким образом увеличивая вероятность того, что два документа, которые похожи, получат одну и ту же подпись. Например, если два документа похожи на 80%, тогдавероятность того, что они получат одинаковую подпись от одной функции LSH, составляет 80%. Однако если мы используем несколько функций LSH, тоs более высокий шанс получить одинаковую подпись для документов с помощью одной из функций 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) !!!