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

Question

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

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

1. Использование kd-дерева навсегда привязывает меня к евклидову расстоянию ?
2. Если да, то какие другие виды алгоритмов мне следует попробовать, чтобы это работало для произвольных метрик ? У меня нет времени на реализацию множества различных структур данных, но я думаю о других структурах: деревья покрытия и vp-деревья .

Answer 1

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

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

Answer 2

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