Я пытаюсь понять раздел 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 ответ:

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

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

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

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