Как осуществлять поиск ближайших элементов в многомерном пространстве?

Question

[hateyyyy]

Здравствуйте, имеется задача поиска в многомерных данных ближайших объектов.
В геолокации знаю, что используют вариации R-дерева, а если объекты имеют 6 признаков, оно сойдет?
Есть ли еще альтернативные способы решения данной задачи?
Спасибо.

Answer 1

[xmoonlight]

знаю, что используют вариации R-дерева, а если объекты имеют 6 признаков, оно сойдет?

Сойдёт, если действительно знаете.

Comments

[hateyyyy]

Ну в том то и дело, что в теории в курсе и хотел перед началом работы уточнить, будет ли положительный эффект для 6 признаков)

[xmoonlight]

hateyyyy: давайте вначале поймём: что нам известно про R-деревья и их вариации? Как лично Вы видите решение?

Answer 2

[vasiliev]

Список подходов можно посмотреть в вики.

Ближайшие соседи бывают разные: ближайший для конкретной точки или ближайшие 2 точки по всему объёму. Кроме того, важны требования по быстродействию и объёмы данных: если вам не нужен 100% точный результат, то есть много методов, ищущих хорошее приближение. Так, в библиотеке flann есть неплохие реализации таких алгоритмов на базе kdtree, которые справляются с размерностями гораздо больше, чем 6.

Из альтернатив есть LSH, но для такой размерности я бы в первую очередь смотрел на деревья.