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

Question

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

k-d Дерево, возможно, самое популярное решение для решения NN.

Однако чтение this survey я нашел эти структуры, и я не понимаю, какие из них для решения NN или ИНС:

• четверной/OCT-дерево
• мяч дерево
• R-Tree
• M-Tree

я не нашел ни одного опроса, посвященного ИНС, так что я думаю, что все это для NN и встретились ric (они не могут использоваться для неметрических пространств).

Answer 1

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

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

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

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