Как создать хэши, чувствительные к локальности? - PullRequest
Новая
       8

Как создать хэши, чувствительные к локальности?

5 голосов
/ 30 июня 2011

У меня уже есть алгоритм для создания хеш-кодов, чувствительных к локальности, но как мне их объединить, чтобы воспользоваться их характеристиками (т. Е. Аналогичные элементы имеют близкие хэши (с расстоянием Хэмминга))?

В коде Matlab, который я обнаружил, они просто создают матрицу расстояний между хешами точек для поиска и хешами точек в базе данных, чтобы упростить код, ссылаясь на так называемый метод Чарикарана самом деле хорошая реализация метода поиска.

Я пытался найти это, но я не уверен, как применить к моему случаю любой из найденных мной методов (например, метод с несколькими зондами).Ни один из этих методов не кажется легко подключаемым, если у вас уже есть хэши.Есть ли простой пример кода для этого?Или любое предложение?

Это ссылка на страницу с кодом Matlab, о котором я говорю: http://www.eecs.berkeley.edu/~kulis/klsh/klsh.htm

1 Ответ

0 голосов
/ 23 мая 2016

На основе: Поиск в локально-чувствительном хешировании Я бы сказал это после прочтения Методы оценки подобия из алгоритмов округления :

Этот вопрос довольно широкий, поэтому я просто приведу здесь минимальный (абстрактный) пример:

У нас есть 6 (= n) векторов в нашем наборе данных с d битами каждый. Давайте предположим, что мы делаем 2 (= N) случайной перестановки.

Пусть начнется первая случайная перестановка! Помните, что мы переставляем биты , , а не порядок векторов . После перестановки битов они поддерживают порядок, например: 

v1
v5
v0
v3
v2
v4

Теперь прибывает вектор запроса, q, но маловероятно, что он будет таким же с вектором в нашем наборе данных (после перестановки), поэтому мы не будем найдите его, выполнив бинарный поиск.

Однако мы окажемся между двумя векторами. Итак, теперь мы можем представить себе такой сценарий (например, q лежит между v0 и v3: 

v1
v5
v0 <-- up pointer
   <-- q lies here
v3 <-- down pointer
v2
v4

Теперь мы перемещаем указатель вверх или вниз, ища вектор vi, который будет соответствовать большинству битов с q. Допустим, это был v0.

Точно так же мы делаем вторую перестановку и находим вектор vi, скажем, v4. теперь мы сравним v0 из первой перестановки и v4, чтобы увидеть, какая из них ближе всего к q, то есть какая из них имеет наибольшее число битов, равное q.

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

...