Найти единственного ближайшего соседа, используя дерево префиксов в O(1)?

Question

Я читаю статью, где они упоминают, что им удалось найти единственного ближайшего соседа в 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): Получение толпы на основе контента в Интернете в реальном времени.

http://students.cse.tamu.edu/kykamath/papers/cikm2012/fp105-kamath.pdf

Я также хотел бы, чтобы вы могли ответить на мой другой вопрос, связанный с этим: Как найти наиболее похожий битовый вектор в дереве префиксов для NN-поиска?

Answer 1

Я думаю, что аргумент в статье заключается в том, что если бы это было O(f(x)), то x должно быть числом элементов, хранящихся в дереве, а не количеством измерений. Как вы указали, для дерева префиксов время увеличивается как O(M), где M - длина битового вектора, но если вы считаете, что M фиксировано, и вас интересует поведение как числа элементов в дерево увеличивается, у вас есть O(1).

Кстати, в статье Muja и Lowe "Быстрые приближенные ближайшие соседи с автоматической настройкой алгоритма" также рассматриваются основанные на деревьях конкуренты для LSH. Идея здесь состоит в том, чтобы рандомизировать конструкцию дерева, создать несколько деревьев и выполнить быстрый, но схематичный поиск каждого дерева, выбирая лучший ответ, найденный в любом дереве.

Answer 2

Это O(1) только в очень слабо определенном смысле. На самом деле я бы пошел так далеко, что оспаривал их использование в этом случае.

Из их бумаги, чтобы определить ближайшего соседа к пользователю, u,

1. "Сначала мы рассчитаем его подпись, u": может быть O(1) в зависимости от "подписи"
2. "Тогда для каждого префикса дерева в P"О, не звучит очень O(1), O(P) было бы правильнее.
3. итерационная часть из 2. "... мы находим ближайшую сигнатуру в дереве префиксов, перебирая дерево по одному уровню за раз...": лучший случай O(d) где d это глубина дерева или длина слова. (это щедро, так как поиск ближайшей точки в дереве префиксов может быть больше, чем это)
4. "После этого... мы в конечном итоге |P| подписи... из которых выбрано наименьшее расстояние Хемминга ": так другое P расчет умножить на длину слова. O(Pd),

Вернее, общее время выполнения O(1) + O(P)+ O(Pd) + O(Pd) = O(Pd)

Я считаю, что @mcdowella прав в своем анализе того, как они пытаются это сделать. O(1)Но из того, что я прочитал, они не убедили меня.

Answer 3

Я предполагаю, что они имеют ссылку на узел P в дереве и могут перейти к следующей или предыдущей записи за O(1) амортизированное время. трюк в том, чтобы иметь доступ к базовым узлам.