Измените этот алгоритм для поиска ближайшего соседа (NNS) для выполнения Approximate-NNS

Question

Из слайдов курса я нашел следующие:

Для заданного множества P в R^D и точки запроса q это NN - точка p_0 в P, где:

dist(p_0, q) <= dist(p, q), for every p in P.

Аналогично, с коэффициентом аппроксимации 1 > ε > 0 ε-NN равен p_0, так что:

dist(p_0, q) <= (1+ε) * dist(p, q), for every p in P.

(Интересно, почему ε не может достичь 1).

Мы строим KD-дерево и затем ищем NN с помощью этого алгоритма:это правильно, насколько мой разум и мои испытания.

Как я должен изменить вышеупомянутый алгоритм, чтобы выполнить Приблизительный поиск ближайшего соседа (ANNS)?

Моя мысль состоит в том, чтобы умножить текущее значение (в части обновления в листе) на ε и оставить остальную часть алгоритма как есть. Я не уверен, однако, если это правильно. Может кто-нибудь объяснить?

PS - Я понимаю, как работает поиск NN.

Обратите внимание, что я спросил на сайте Computer Science, но ничего не получил!

Answer 1

Одна модификация, необходимая для замены current best distance с current best distance/(1+ε), Это сокращает узлы, которые не могут содержать точку, нарушающую новое неравенство.

Причина того, что это работает, заключается в том, что (при условии, что cut-coor(q) находится на левой стороне) тест

cut-coor(q) + current best distance > node's cut-value

проверяет, разделяет ли гиперплоскость left-child а также right-child ближе чем current best distance, что является необходимым условием для точки в right-child быть ближе к точке запроса q, так как отрезок соединяется q и точка в right-child проходит через эту гиперплоскость. Заменяя d(p_0, q) = current best distance с current best distance/(1+ε)мы проверяем, есть ли точка p на правой стороне мог удовлетворить

d(p, q) < d(p_0, q)/(1+ε),

что эквивалентно

(1+ε) d(p, q) < d(p_0, q),

что является свидетельством нарушения приблизительной гарантии ближайшего соседа.