Как разрешить ближайшего соседа через ближайшего соседа R?

Question

Приводя руководство E2LSH (это не важно, что это об этой конкретной библиотеке, эта цитата должна быть верна для задачи NN вообще):

E 2LSH также может быть использован для решения ближайшей проблемы соседа, где , с учетом запроса q, для структуры данных требуется отчет в точке в P, ближайшей к q. Это можно сделать, создав несколько соседних структур данных R-near , для R = R1, R2,. , , Rt, где Rt должно быть больше максимального расстояния от любой точки запроса до ближайшего соседа . Ближайший сосед может быть затем извлекали запрашивая структуры данных в возрастающем порядке radiae, остановки всякий раз, когда первая точка находится

Может кто-то перефразировать это, пожалуйста? Я не пытаюсь найти ближайшего соседа по подходу R-near neighbour.

Answer 1

Я приведу пример, который должен прояснить ситуацию. Предположим, что наш набор данных состоит только из одной точки, p и появляется точка запроса, q. Предположим, что расстояние p и q составляет 3,9.

Теперь, используя E2LSH ^$, я могу создать структуру данных, которая решает R-ближайший сосед проблему, то он будет отвечать да (и принесите мне точку), что лежит внутри радиуса R. Если нет такого точка существует, ответ будет отрицательным.

Допустим, я выбираю построить 5 структур данных такого рода, начиная с R = 1 до 5. В нашем сознании, это то, что мы делали до сих пор:

Так что теперь помните, что d (p, q) = 3,9, поэтому мы ожидаем спросить структуру данных, которая построена с R = 4 и найти для нас точку запроса q.

Теперь давайте притворимся, что мы не знаем d (p, q), поэтому мы начинаем поиск с самого маленького радиуса, который мы выбрали, это 1. Итак, мы спрашиваем: есть ли что-либо в радиусе (равном 1) из наш набор данных? Нет!

От R = 2? Нет! От R = 3? Нет! От R = 4? Да, и это q! Итак, теперь мы закончили. 4 - R _t Вы упомянули в своем вопросе.

---

* _{Это сильное предположение и E2LSH страдает для того, чтобы положить пользователю ввести этот параметр R, так как обычно мы не знаем, какое значение R есть, слишком большой, и мы будем тратить пространство и время, слишком мало, и мы не найдем наш запрос!}

$ _{Я слышал, что есть что-то более современное, чем E2LSH сейчас, на главной странице Ilya Razenshteyn.}