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

Question

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

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

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

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

Answer 1

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

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

У нас 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,

---

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