Поиск в локальном хешировании

Question

Я пытаюсь понять раздел 5. этой статьи о LSH, в частности, как создать сгенерированные хэши. Цитирую связанный документ:

Учитывая битовые векторы, состоящие из d битов каждый, мы выбираем N = O(n 1/(1+epsilon)) случайных перестановок битов. Для каждой случайной перестановки σ мы поддерживаем отсортированный порядок O σ битовых векторов в лексикографическом порядке битов, переставляемых σ. Для заданного вектора битов запроса q мы находим приблизительного ближайшего соседа, выполняя следующие действия: Для каждой перестановки σ мы выполняем двоичный поиск по O σ, чтобы найти два битовых вектора, ближайших к q (в лексикографическом порядке, полученном в результате). битами, переставленными σ). Теперь мы ищем в каждом из отсортированных порядков O σ, исследуя элементы выше и ниже позиции, возвращаемой двоичным поиском, в порядке длины самого длинного префикса, который соответствует q. Это можно сделать, поддерживая два указателя для каждого отсортированного порядка O σ (один перемещается вверх, а другой - вниз). На каждом шаге мы перемещаем один из указателей вверх или вниз, соответствующий элементу с самым длинным совпадающим префиксом. (Здесь длина самого длинного совпадающего префикса в O σ вычисляется относительно q с его битами, переставленными σ). Таким образом, мы исследуем 2N = O(n 1/(1+ эпсилон)) битовых векторов. Из всех рассмотренных битовых векторов мы возвращаем тот, который имеет наименьшее расстояние Хемминга, к q.

Я запутался в этом алгоритме и не думаю, что понял, как он работает.

Я уже нашел этот вопрос по теме, но я не понял ответа в комментариях. Также в этом вопросе в пункте 2 описан тот же алгоритм, но опять же, я не понимаю, как он работает.

Не могли бы вы попытаться объяснить мне, как это работает, шаг за шагом, пытаясь быть как можно более простым?

Я даже пытался составить список вещей, которые я не понимаю, но на практике написано так плохо, что я не понимаю большинство предложений!

РЕДАКТИРОВАТЬ после gsamaras ответ:

Я в основном понял ответ, но у меня все еще есть некоторые сомнения:

1. Правильно ли говорить, что общая стоимость выполнения N перестановки O(Nnlogn), так как мы должны отсортировать каждого из них?

2. Описанный выше процесс перестановки + сортировки выполняется только один раз во время предварительной обработки или для каждого запроса q? Кажется, уже довольно дорого O(Nnlogn) даже при предварительной обработке, если мы должны сделать это во время запроса, это катастрофа:D

3. В последний момент, где мы сравниваем v0 а также v4 в q, мы сравниваем их перестановочную версию или оригинальную (до их перестановки)?

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,

---

Редактировать:

Правильно ли говорить, что общая стоимость выполнения N перестановок равна O(Nnlogn), поскольку мы должны отсортировать каждую из них?

Если они на самом деле сортируют каждую перестановку с нуля, тогда да, но мне не ясно, как они это делают.

Описанный выше процесс перестановки + сортировки выполняется только один раз во время предварительной обработки или для каждого запроса q?

ОДИН РАЗ.

В последний момент, где мы сравниваем v0 а также v4 в q, мы сравниваем их перестановочную версию или оригинальную (до их перестановки)?

Я думаю, что они делают это с переставленной версией (см. Скобки перед 2N в газете). Но это не имеет никакого значения, так как они переставляют q тоже с той же перестановкой (σ).

---

Этот ответ может также пролить свет.