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

Question

LSH - это популярный алгоритм для ANN.

kd Tree, пожалуй, самое популярное решение для точного решения NN.

Однако, читая этот опрос, я обнаружил эти структуры и не понимаю, какие из них предназначены для решения NN или ANN:

• четырехъядерный / Октябрь-дерево
• шар-дерево
• R-Tree
• M-Tree

Я не нашел ни одного обзора, посвященного ANN, поэтому я думаю, что все они предназначены для NN и для метрических пространств (их нельзя использовать для неметрических пространств).

Answer 1

Во-первых, позвольте мне подтвердить, что дерево квадрантов, шаровое дерево, R-дерево и M-дерево могут использоваться для поиска ближайшего соседа (NNS).

Теперь, если структура может поддерживать NNS, то она может поддерживать приблизительный поиск ближайшего соседа.

Возьмите, к примеру, kd-дерево, которое вы, возможно, знаете лучше; он собирает баллов-кандидатов, которые могут быть ответом на запрос. Если вы проверите все возможные кандидаты, то сможете ответить на точный запрос ближайшего соседа. Если вы проверите некоторых кандидатов, то сможете ответить на приблизительный запрос ближайшего соседа.

Надеюсь, это поможет!:)