Могу ли я использовать произвольные показатели для поиска KD-Trees?

Question

Я только что закончил реализацию kd-tree для быстрого поиска ближайших соседей. Мне интересно играть с разными показателями расстояния, отличными от Euclidean distance. Мое понимание kd-дерева заключается в том, что быстрый поиск kd-деревьев не гарантирует точный поиск, если метрика неевклидова, что означает, что мне может потребоваться реализовать новую структуру данных и алгоритм поиска, если я хочу попробовать вывести новые показатели для моего поиска.

У меня есть два вопроса:

1. ли с помощью kd-tree постоянно привязывают меня к Euclidean distance?
2. Если да, то какие другие виды алгоритмов я должен попробовать, чтобы работать на произвольные metrics? У меня нет много времени для реализации множества различных структур данных, но другие структуры, о которых я думаю, включают cover trees и vp-trees.
процедура поиска

Answer 1

ближайшего соседа описано на странице Википедии вы связаны, конечно, можно обобщить на другие показатели расстояния, при условии замены «гиперсферу» с эквивалентным геометрическим объектом для данной метрики, и проверить каждую гиперплоскость для пересечения с этим объектом.

Пример: если вы используете Манхэттенское расстояние (т. Е. Сумму абсолютных значений всех различий в векторных компонентах), ваша гиперсфера станет (многомерным) алмазом. (Это проще всего визуализировать в 2D - если ваш ближайший ближайший сосед находится на расстоянии x от точки запроса p, то любой более близкий сосед за другой гиперплоскостью должен пересекать алмазную форму с шириной и высотой 2x и с пометкой p). Это может затруднить выполнение теста перекрестного пересечения с более сложными для программирования или медленнее, однако общий принцип все же применяется.

Answer 2

Я не думаю, что вы привязаны к эвклидовому расстоянию - как говорит j_random_hacker, вы, вероятно, можете использовать расстояние Манхэттена, но я уверен, что вы привязаны к геометриям, которые могут быть представлены в декартовых координатах. Таким образом, вы не можете использовать kd-дерево для индексации метрического пространства, например.