Добрый день, есть необходимость найти эффективный вероятностный алгоритм поиска k ближайших соседей.
Рассматриваем точки в 3-мерном  пространстве, в качестве расстояния берем Евклидову метрику.
На данный момент я нашел следующие алгоритмы:  random projection kd-trees, GNNS, LSH, randomized kd-tree. 
Возможно, что кто-то сможет посоветовать другие. Нужно улучшить оценку O(nlogn). Заранее спасибо за ваши ответы.

эффективный то по точности или по времени?

на самом деле я ответа не знаю, но мне эта тематика тоже интересна.

из готовых библиотек 
ANN http://www.cs.umd.edu/~mount/ANN/ 
сейчас её использую для 2D(использую для radius search,) напрягает только старый интерфейс и еще то, что даже если ищешь точно, то выдает неточные результаты, там в мануале вроде бы про это что то даже написано, но я так и не понял с чем это связано.

FLANN http://www.cs.ubc.ca/~mariusm/index.php/FLANN/FLANN
пробовал ту что встроена в opencv, там не было radius search и я забил.
а вообще выглядит более свежо.

STANN https://sites.google.com/a/compgeom.com/stann/Home

Эффективный по времени.

ANN http://www.cs.umd.edu/~mount/ANN/ - я так понимаю здесь не используются вероятностные алгоритмы.
Получается оценка поиска соседей для одной частицы по времени порядка O(logn).

FLANN http://www.cs.ubc.ca/~mariusm/index.php/FLANN/FLANN - здесь смысл в выборе подходящего алгоритма по входным данным, там упоминается интересный алгоритм Randomized kd-trees (его оценка O(klog(n/k)), где k - количество kd-tree, число которых обычно делают степенью 2)

STANN https://sites.google.com/a/compgeom.com/stann/Home - не понял, какой алгоритм используется внутри, вы не знаете?

Я думаю, что можно попробовать понизить оценку с помощью модификаций алгоритмов GNNS и LSH, вы с этими алгоритмами не сталкивались?

Интересная статья http://yury.name/algoweb/05algoweb.pdf, пытаюсь разобраться в сложности поиска.

Это сообщение отредактировал(а) fandorin - 12.12.2012, 16:05

Согласно статье http://yury.name/algoweb/05algoweb.pdf сложность поиска получается порядка O(n^ro), где ro < 1, но тогда выходит асимптотика даже хуже получается, либо я что-то не так понял.

что такое GNNS вообще не нашел, а  LSH помоему не выдает K ближайших, а просто группирует несколько в одну ячейку типа кластеризации.

Это сообщение отредактировал(а) mrgloom - 12.12.2012, 16:22

GNNS - http://webdocs.cs.ualberta.ca/~zhang/GNNS.pdf, подход основан на построении k-NN графа.

В LSH мы получаем ячейку, они это называют списком кандидатов, а затем бежим по списку и уже точно вычисляем k соседей.