Как найти ближайшие 2 точки в 100-мерном пространстве с 500 000 точек?

Question

У меня есть база данных с 500 000 точек в 100-мерном пространстве, и я хочу найти ближайшие 2 точки.Как мне это сделать?

Обновление: Пространство евклидово, извинитеИ спасибо за все ответы.Кстати, это не домашнее задание.

Answer 1

В главе Введение в алгоритмы * есть глава , посвященная поиску двух ближайших точек в двумерном пространстве за O (n * logn) времени. Вы можете проверить это на Google Книги . На самом деле, я предлагаю это всем, так как метод решения проблемы «разделяй и властвуй» очень прост, элегантен и впечатляет.

Хотя это не может быть расширено непосредственно к вашей проблеме (так как константа 7 будет заменена на 2^101 - 1), для большинства наборов данных это должно быть просто отлично. Таким образом, если у вас достаточно случайный ввод, он даст вам O(n*logn*m) сложность, где n - это количество точек, а m - это число измерений.

редактировать
Это все, если у вас есть евклидово пространство. Т.е. длина вектора v равна sqrt(v0^2 + v1^2 + v2^2 + ...). Если вы можете выбрать метрику, однако, могут быть другие варианты для оптимизации алгоритма.

Answer 2

Используйте дерево кд.Вы смотрите на проблему ближайшего соседа, и есть высоко оптимизированные структуры данных для обработки именно этого класса проблем.

http://en.wikipedia.org/wiki/Kd-tree

PS Забавная проблема!

Answer 3

Запустите PCA для ваших данных, чтобы преобразовать векторы из 100 измерений в 20 измерений.Затем создайте дерево ближайших соседей (KD-дерево) и найдите двух ближайших соседей на основе евклидова расстояния.

Обычно, если нет.измерений очень велики, то вы должны либо использовать метод грубой силы (параллельный + распределенный / картографический) или кластерный подход.

Answer 4

Вы можете попробовать библиотеку ANN , но это дает надежные результаты только до 20 измерений.

Answer 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