Вопрос к крутым data architect-ам и примазывающимся

[Marmot]

Нужно сделать не вполне тривиальную вещь: многомерный индех для векторов с размерностью N>100.
Есть ли сейчас на рынке продукты которуе позволяют такое дело поиметь?
Если нет, то в сторону каких алгоритмов лучше начинать копать?

[Stanislav]

Да уж не на моделирование ли фазового пространства души замахнулись?

[ura]

Не - наверное real state - вот где деньги то сейчас.
Или online gamling.

[Marmot]

Да уж не на моделирование ли фазового пространства души замахнулись?

Я бы так сказал - душёнок, в основном любителей нелегального порно, ну и других заодно посчитаем
Только вот как бы это в ДБ засунуть да проиндексировать...

[aissp]

А что надобно точно? Распознать ли близки две точки в многомерном пространтсве? етот индекс нужен? Типа найти все точки которые принадлежат многомерному кубу (ну или там не кубу)? Найти все точки близкие к N-1 поверхности?

Или просто 100 индексов?

[Marmot]

Типа найти все точки которые принадлежат многомерному кубу

Вот именно это, и желательно побыстрее, для порядка 10^9 точек...

[Sheen]

Не в тему (из одной переписки):

Есть многомерные индексы.
Но под ними понимают кто чего хочет )

Индекс номер раз - реализован в СУБД Cach'e. Это реальный многомерный массив. Причем разреженный. Там есть классная математика. У моей жены один знакомый занимался какраз разреженными массивами. Уехал в Лондон по-моему. Там математика такая что очень хорошо ложится на машинные алгоритмы и дает огромные скорости и сами алгоритмы очень красивые.

Индекс номер два - это снижение размерности индекса. Я про это кое-что знаю, т.к. занимался много ГИСами. Смысл в том, что на скажем карте у точки есть две координаты. Но можно с помощью разных ухищрений преобразовать объек на двумерной плоскости в одноменую прямую, точнее отрезки прямой. Получается многомерный индекс. Если интересно посмотри по словам "z-кривая" или "кривая Гилберта".

Индекс номер три - это различные деревья. Для одномерного случая есть широко известные B-деревья. Для двумерноего есть R-деревья. И т.д. их расширяют на многомерные случаи, но соль в том, что такой индекс не позволяет вести точный поиск, как в B-дереве. Он лишь сужает диапазон поиска, а потом используется полный перебор по этому диапазону и алгоритм точного сравнения данных.

[vg]

Типа найти все точки которые принадлежат многомерному кубу

Вот именно это, и желательно побыстрее, для порядка 10^9 точек...

На самом деле очень может быть важная задача, например, в задачах поиска экстремума сложных функций цели. Единственно, что могу сказать, что, например, оптимизация по такому числу параметров говорит о том, что модель - сакс. Может с этой стороны зайти и затем уменьшить 100 до 5?

ПС. Строгин решал многомерные непарамертрические задачи при помощи "развёрток" n-многомерных кубов (при получении развёртки n-мерная задача сводится к одномерной). Посмотри в эту сторону.

[aissp]

А метрика на пространстве то задана? Типа возьмем два больных у одного понос и желтуха, у второго типа геморой и триппер. К кому ближе больной у которого диабет и склероз? Мне просто интересно (честно гря ужасно) откуда растут хвосты етой задачи

[sz]

По моему, ключевое слово R-tree index. Их используют для поиска принадлежности точки региону, и еще, кажется для индексирования подстрок в словах. А подробностей не помню.

Помню, что в postgress sql они поддерживаются. Про остальных - не знаю.

[vg]

А метрика на пространстве то задана? Типа возьмем два больных у одного понос и желтуха, у второго типа геморой и триппер. К кому ближе больной у которого диабет и склероз? Мне просто интересно (честно гря ужасно) откуда растут хвосты етой задачи

Положим задана, так что можно определить "расстояние" от точки до заданной в n-мерном пространстве. При большом чиcле точек и большой размерности - может CPU сгореть?

ПС. Такое расстояние следует понимать как степень удалённости точки от других. Это не самтиметры.

[aissp]

Я пока только уточняю формулирвку задачи, без вынесения рецептов и поиса лекарст, мне интересно узнать постановку. Делать предположения чего и как могет сгореть сантиметры ето или другие единицы? Лучше у аффтара спросить он точно знает из какой области задача, а на дапускать я и сам гораз полные штаны таким вот полетом

[vg]

Мне самому интересно. Как эффективно и просто решить задачу пусть в простейшем случае, для N - "вещественных" измерений и M - точек. Найти n-ближайших соседей, или определить таковых по заданному радиус-вектору. Если вычислять радиус-вектор до каждой точки, чтоб найти n-ближайших соседей случайной точки - это долго.
Поэтому генерируовать точки надо так, чтобы индекс Marmot-това простанства обновлялся при генерации, т. е автоматически.

[Stanislav]

... Marmot-това простанства .....

А красиво получилось! Marmot-тово простанство - звучит!!!

[aissp]

много всяких R tree brep three kdb tree кирвая гилбьерта/ я сталкивался тока с R tree насколкьо я знаю успешных проектов использование R деревбев для измерений больше трех не было. Ну и спич идет о пространстве равномерно заполненным точками. Поетому честно говоря ответить мне нечегоЮ а вот ответы услышать интересно=)