Здравствуйте, _DeKa_, Вы писали:

_DK>Т.е. в псевдокоде хочется получить что-то вроде: SELECT first N FROM table ORDER BY distance_to(query)
ООО!
_DK>Собственно вопрос: как лучше это реализовать, если хранить дескрипторы в базе (а не просто в памяти). СУБД — пока что SQLite, но в дальнейшем возможен переход на MSSQL. Объектов в базе при среднем использовании 20-50.000 Но должно работать с приемлимой скоростью и на 100.000 объектов. Приемлимая скорость это 1-2 секунды для одного запроса при 20.000 объектов.
Ну, по большому счёту, современная наука для случая высоких размерностей ничего интересного предложить не может.
Для двух- и трёхмерного случая есть R-tree индексы; они немножко помогают. Но для высоких размерностей древовидные индексы быстро начинают сливать (АФАИК, уже при 10-12 измерениях линейный поиск получается быстрее).

Поэтому, если хочется получить реальное решение, то стоит копать в сторону оптимизации линейного просмотра.
Давайте прикинем: вот у нас 1*10^5 объектов, 1*10^3 атрибутов. Итого — 1*10^8. Если атрибуты вещественные, т.е. 8 байт, то характерный размер всей кучи — 10^9 байт, или около одного гига. В принципе, ничего военного при нынешних размерах ОП на серверах.
То есть, можно заточиться на то, что весь кэш помещается в память, и плясать от этого. Померьте, хватит ли современного процессора для обеспечения приемлемого быстродействия.
Преимущество решения — можно относительно быстро наколбасить прототип, который будет работать. Потом можно относительно неспешно заниматься оптимизацией серверной части, сохраняя протокол взаимодействия с клиентом.

Дальше я бы копал в сторону кластерного анализа. В первую очередь — в сторону иерархической кластеризации. http://en.wikipedia.org/wiki/Hierarchical_clustering,
http://www.cs.gsu.edu/~wkim/index_files/papers/sibson.pdf