Каковы некоторые быстрые приближения ближайшего соседа?

Question

Скажем, у меня есть огромный (несколько миллионов) список из n векторов, учитывая новый вектор, мне нужно найти довольно близкий из набора, но он не должен быть самым близким.(Ближайший сосед находит ближайший и запускается за n раз)

Какие существуют алгоритмы, которые могут очень быстро приблизить ближайшего соседа за счет точности?

РЕДАКТИРОВАТЬ: Поскольку это, вероятно, поможет, яследует упомянуть, что данные в большинстве случаев довольно гладкие, с небольшой вероятностью появления колючек в случайном измерении.

Answer 1

Существуют более быстрые алгоритмы, чем O (n), для поиска ближайшего элемента по произвольному расстоянию. Проверьте http://en.wikipedia.org/wiki/Kd-tree для деталей.

Answer 2

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

Докторская диссертация Вей Донга (http://www.cs.princeton.edu/cass/papers/cikm08.pdf) может помочь вам найти обновленный алгоритм поиска KNN, т. Е. LSH. Отличается от более традиционного LSH, такого как E2LSH (http://www.mit.edu/~andoni/LSH/), опубликованного ранее MIT Исследователи, его алгоритм использует мульти-зондирование, чтобы лучше сбалансировать компромисс между скоростью отзыва и стоимостью.

Answer 3

Для приблизительного ближайшего соседа самым быстрым способом является использование локально-чувствительного хеширования (LSH).Есть много вариантов ЛСГ.Вы должны выбрать один в зависимости от метрики расстояния ваших данных.Big-O времени запроса для LSH не зависит от размера набора данных (не считая времени для выходного результата).Так что это действительно быстро.Эта библиотека LSH реализует различные LSH для пространства L2 (евклидова).

Теперь, если размерность ваших данных меньше 10, предпочтительным будет дерево kd хочу точный результат.

Answer 4

Поиск в сети по библиотеке lsh "ближайший сосед" находит http://www.mit.edu/~andoni/LSH/ http://www.cs.umd.edu/~mount/ANN/ http://msl.cs.uiuc.edu/~yershova/MPNN/MPNN.htm