Быстрый способ вычисления минимального расстояния двух наборов k-мерных векторов

Question

I два набора k-мерных векторов, где k составляет около 500, а количество векторов обычно меньше. Я хочу вычислить (произвольно определенное) минимальное расстояние между двумя наборами. Наивный подход был бы такой:

(loop for a in set1
      for b in set2
      minimizing (distance a b))

Однако для этого требуются вычисления O (n² * distance). Есть ли более быстрый способ сделать это?

Answer 1

Я не думаю, что вы можете добиться большего успеха, чем O (n ^ 2), когда расстояние произвольно (вы должны изучить каждое из возможных расстояний!). Для данной функции расстояния мы могли бы использовать свойства функции, но не будет никакого общего алгоритма, который работает с любой функцией расстояния лучше, чем O (n ^ 2) (то есть o (n ^ 2): примечание smallOh).

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

• http://www.ics.uci.edu/~eppstein/projects/pairs/Papers/Epp-SODA-98.pdf. [O (nlog ^ 2 (n)) время обновления]

• http://academic.research.microsoft.com/Paper/1847461.aspx

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

Для расстояния евклидова типа (L ^ p) существуют известные алгоритмы времени O (nlogn), которые работают с заданным набором точек (т. Е. Вам не нужны какие-либо специальные алгоритмы обновления):

• http://www.cse.iitd.ernet.in/~ssen/cs852/scribe/scribe2/lec.pdf
• http://en.wikipedia.org/wiki/Closest_pair_of_points_problem

Конечно, L ^ p для одного набора, но вы можете адаптировать его для двух наборов.

Если вы дадите функцию расстояния, может быть проще для нас.

Надеюсь, это поможет. Удачи!

Answer 2

Поместите два набора координат в Пространственный индекс , например. KD-дерево .

Затем вы вычисляете пересечение этих двух индексов.

Answer 3

Если компоненты ваших векторов являются скалярами, я бы предположил, что для вашего случая умеренного k = 500 подход O (n²), вероятно, настолько быстр, насколько вы можете получить. Вы можете упростить свой расчет, уменьшив расстояние². Кроме того, расстояние (A_i, B_i) = расстояние (B_i, A_i), поэтому убедитесь, что вы сравниваете их только один раз (у вас есть только 500! / (500-2)! Пар, а не 500²).

Если компоненты являются m-мерными векторами A и B, вы можете сохранить компоненты вектора A в R-дереве или kd-дереве , а затем найти ближайшую пару, перебирая все компоненты вектора B и находя ближайшего партнера из A --- это будет O (n). Не забывайте, что big-O предназначен для n-> бесконечности, поэтому деревья могут иметь довольно дорогой постоянный член (то есть такой подход может иметь смысл только для больших k или если вектор A всегда одинаков).