У меня есть база данных с 500 000 точек в 100-мерном пространстве, и я хочу найти ближайшие 2 точки. Как это сделать?
Обновление: Пространство - евклидово, Извините. И спасибо за все ответы. Кстати, это не домашнее задание.
Как найти ближайшие 2 точки в 100-мерном пространстве с 500 000 точек?
Ответ 1
Ответ 2
В главе Введение в алгоритмы посвящена поиск двух ближайших точек в двумерном пространстве в O (n * logn) времени. Вы можете проверить это на google books. На самом деле, я предлагаю это для всех, так как они применяют технику разделения и покорения к этой проблеме очень просто, элегантно и впечатляюще.
Хотя он не может быть распространен непосредственно на вашу проблему (поскольку константа 7 будет заменена на 2^101 - 1), это должно быть прекрасно для большинства наборов данных. Итак, если у вас есть разумно случайный ввод, это даст вам O(n*logn*m) сложность, где n - количество точек, а m - количество измерений.
изменить
Все это предполагает, что у вас есть евклидово пространство. I.e, длина вектора v равна sqrt(v0^2 + v1^2 + v2^2 + ...). Однако, если вы можете выбрать метрику, могут быть другие варианты оптимизации алгоритма.
Ответ 3
Запустите PCA на своих данных, чтобы преобразовать векторы из 100 измерений, чтобы сказать 20 измерений. Затем создайте K-Nearest Neighbor tree (KD-Tree) и получите ближайших 2 соседей на основе эвклидовой дистанции.
Обычно, если нет. размеров очень велики, тогда вам нужно либо выполнить подход грубой силы (параллельно + распределить/уменьшить карту), либо использовать кластерный подход.
Ответ 4
Используйте дерево kd. Вы смотрите на проблему ближайшего соседа, и для обработки этого точного класса проблем существуют высоко оптимизированные структуры данных.
http://en.wikipedia.org/wiki/Kd-tree
P.S. Забавная проблема!
Ответ 5
Используйте структуру данных, известную как KD-TREE. Вам нужно будет выделить много памяти, но вы можете обнаружить оптимизацию или две по пути на основе ваших данных.
http://en.wikipedia.org/wiki/Kd-tree.
Мой друг работал над своей докторской диссертацией много лет назад, когда он столкнулся с подобной проблемой. Его работа была порядка 1 М пунктов по 10 измерениям. Для его решения мы построили библиотеку kd-tree. Возможно, мы сможем откопать код, если вы хотите связаться с нами в автономном режиме.
Вот его опубликованная статья: http://www.elec.qmul.ac.uk/people/josh/documents/ReissSelbieSandler-WIAMIS2003.pdf