Я читаю статью, в которой упоминается, что они смогли найти единственного ближайшего соседа в O (1), используя префиксное дерево. Я опишу общую проблему, а затем классическое решение и, наконец, предлагаемое решение в статье:
Проблема: учитывая список битовых векторов L (все векторы имеют одинаковую длину) и битовый вектор запроса q, мы хотели бы найти ближайшего соседа q. Метрика расстояния - это расстояние Хэмминга (сколько бит различается). Наивный подход заключался бы в том, чтобы просмотреть список и вычислить расстояние Хэмминга между каждым вектором в списке и q, что займет O (N). Однако, учитывая, что у нас будет миллионы битовых векторов, это очень дорого, поэтому мы хотели бы сократить это количество.
Классическое решение: классическое решение этой проблемы заключается в использовании приближения для поиска ближайшего соседа и достижения O (logN). Для этого сначала нужно отсортировать L лексикографически, чтобы похожие битовые векторы были близки друг к другу. Затем, учитывая q, мы применяем двоичный поиск в отсортированном списке, чтобы получить позицию, где q может быть в отсортированном списке, и берем векторы над ним и под ним в списке (поскольку они похожи из-за сортировки) и вычисляем расстояние между ними и выберите тот, у которого наименьшее расстояние. Однако, просто выполняя одну сортировку, мы все равно пропустим много похожих векторов, поэтому, чтобы охватить как можно больше похожих векторов, мы используем P количество списков и P количество смешанных функций. Каждому списку соответствует каждая функция перехода. Затем мы вставляем каждый битовый вектор в каждый список в P после смешивания его битов с соответствующей функцией смешивания. Таким образом, мы получаем P списков, каждый из которых имеет битовые векторы, но с разным порядком битов. Мы снова отсортируем каждый список в P лексикографически. Теперь, учитывая q, мы применяем тот же двоичный поиск для каждого списка в P, но здесь мы перед этим применяем функцию перемешивания к q в соответствии с тем, к какому списку мы обращаемся. На этом шаге мы получаем число P векторов, наиболее похожих на q, поэтому мы, наконец, получаем один, наиболее похожий на q. Таким образом мы охватываем как можно больше похожих векторов. При игнорировании времени, необходимого для сортировки, время, необходимое для обнаружения ближайшего соседа, равно O (log n), что является временем двоичного поиска в каждом списке.
Предлагаемое решение: в этом решении, предложенном в статье (но без каких-либо объяснений), говорится, что мы можем получить ближайшего соседа за время O (1), используя префиксные деревья. В документе они сказали, что они используют P число префиксных деревьев и P число функций перемешивания, где каждая функция перемешивания соответствует каждому дереву. Затем они вставляют битовые векторы в каждое дерево после перемешивания битов каждого вектора с соответствующей функцией перемешивания. Для данного q мы применяем функцию перехода к q, соответствующему каждому дереву, и извлекаем наиболее похожий на q вектор из каждого дерева. Теперь мы получаем P-битовые векторы, извлеченные из деревьев. В статье говорится, что просто получение вектора, наиболее похожего на q из префиксного дерева, составляет O (1). Я действительно этого совсем не понимаю, так как знаю, что дерево префиксов поиска - это O (M), где M - длина битового вектора. Кто-нибудь понимает, почему это O (1)?
Это статья, о которой я говорю (Раздел 3.3.2): Content-Based Crowd Retrieval on the Real-Time Web
http://students.cse.tamu.edu/kykamath/papers/cikm2012/fp105-kamath.pdf
Я также хотел бы, чтобы вы ответили на мой другой вопрос, связанный с этим: Как найти наиболее похожий битовый вектор в префиксном дереве для NN-поиска?
