Измените этот алгоритм для поиска ближайшего соседа (NNS) для выполнения Approximate-NNS
Из слайдов курса я нашел следующие:
Для заданного множества 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, но ничего не получил!
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),
что является свидетельством нарушения приблизительной гарантии ближайшего соседа.