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

S>Ну, по большому счёту, современная наука для случая высоких размерностей ничего интересного предложить не может.
S>Для двух- и трёхмерного случая есть R-tree индексы; они немножко помогают. Но для высоких размерностей древовидные индексы быстро начинают сливать (АФАИК, уже при 10-12 измерениях линейный поиск получается быстрее).

Полностью согласен!

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

Собственно говоря, это уже сейчас сделано и нормально работает на тестах. Т.е. все дескрипторы нормально помещаются в память и скорость линейного сравнения, в принципе, устраивает.
Просто у каждого объекта есть еще информация, которая очень хорошо ложится в реляционную структуру. Поэтому и возникла идея все хранить в БД вместе с дескрипторами. Т.е. вопрос в следующем: можно ли организовать такой же линейный поиск, если данные лежат именно в таблице БД? И что конкретно использовать?

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

Это тоже понятно, но с иерархической кластеризацией проблема в том, что при каждом добавлении нового объекта надо перестраивать дерево (в теории дерево может полностью измениться). Кроме того, для ее расчета необходима матрица расстояний каждый с каждым (ну либо пересчет на каждом шаге). При большом количестве объектов это не влезет ни в память, ни в адекватное время. Поправьте меня, если я ошибаюсь.