Страница 1 из 3
Вопрос к крутым data architect-ам и примазывающимся
Добавлено: 16 май 2006, 20:28
Marmot
Нужно сделать не вполне тривиальную вещь: многомерный индех для векторов с размерностью N>100.
Есть ли сейчас на рынке продукты которуе позволяют такое дело поиметь?
Если нет, то в сторону каких алгоритмов лучше начинать копать?
Добавлено: 17 май 2006, 05:47
Stanislav
Да уж не на моделирование ли фазового пространства души замахнулись?
Добавлено: 17 май 2006, 08:59
ura
Не - наверное real state - вот где деньги то сейчас.
Или online gamling.
Добавлено: 17 май 2006, 10:18
Marmot
Stanislav писал(а):Да уж не на моделирование ли фазового пространства души замахнулись?
Я бы так сказал - душёнок, в основном любителей нелегального порно, ну и других заодно посчитаем
Только вот как бы это в ДБ засунуть да проиндексировать...
Вопрос есть
Добавлено: 17 май 2006, 12:22
aissp
А что надобно точно? Распознать ли близки две точки в многомерном пространтсве? етот индекс нужен? Типа найти все точки которые принадлежат многомерному кубу (ну или там не кубу)? Найти все точки близкие к N-1 поверхности?
Или просто 100 индексов?
Re: Вопрос есть
Добавлено: 17 май 2006, 12:37
Marmot
aissp писал(а):Типа найти все точки которые принадлежат многомерному кубу
Вот именно это, и желательно побыстрее, для порядка 10^9 точек...
Добавлено: 17 май 2006, 13:38
Sheen
Не в тему (из одной переписки):
Есть многомерные индексы.
Но под ними понимают кто чего хочет
)
Индекс номер раз - реализован в СУБД Cach'e. Это реальный многомерный массив. Причем разреженный. Там есть классная математика. У моей жены один знакомый занимался какраз разреженными массивами. Уехал в Лондон по-моему. Там математика такая что очень хорошо ложится на машинные алгоритмы и дает огромные скорости и сами алгоритмы очень красивые.
Индекс номер два - это снижение размерности индекса. Я про это кое-что знаю, т.к. занимался много ГИСами. Смысл в том, что на скажем карте у точки есть две координаты. Но можно с помощью разных ухищрений преобразовать объек на двумерной плоскости в одноменую прямую, точнее отрезки прямой. Получается многомерный индекс. Если интересно посмотри по словам "z-кривая" или "кривая Гилберта".
Индекс номер три - это различные деревья. Для одномерного случая есть широко известные B-деревья. Для двумерноего есть R-деревья. И т.д. их расширяют на многомерные случаи, но соль в том, что такой индекс не позволяет вести точный поиск, как в B-дереве. Он лишь сужает диапазон поиска, а потом используется полный перебор по этому диапазону и алгоритм точного сравнения данных.
Re: Вопрос есть
Добавлено: 17 май 2006, 16:17
vg
Marmot писал(а):aissp писал(а):Типа найти все точки которые принадлежат многомерному кубу
Вот именно это, и желательно побыстрее, для порядка 10^9 точек...
На самом деле очень может быть важная задача, например, в задачах поиска экстремума сложных функций цели. Единственно, что могу сказать, что, например, оптимизация по такому числу параметров говорит о том, что модель - сакс. Может с этой стороны зайти и затем уменьшить 100 до 5?
ПС. Строгин решал многомерные непарамертрические задачи при помощи "развёрток" n-многомерных кубов (при получении развёртки n-мерная задача сводится к одномерной). Посмотри в эту сторону.
А гхм а еще вопрос
Добавлено: 17 май 2006, 16:55
aissp
А метрика на пространстве то задана? Типа возьмем два больных у одного понос и желтуха, у второго типа геморой и триппер. К кому ближе больной у которого диабет и склероз? Мне просто интересно (честно гря ужасно) откуда растут хвосты етой задачи
Добавлено: 17 май 2006, 17:20
sz
По моему, ключевое слово R-tree index. Их используют для поиска принадлежности точки региону, и еще, кажется для индексирования подстрок в словах. А подробностей не помню.
Помню, что в postgress sql они поддерживаются. Про остальных - не знаю.
Re: А гхм а еще вопрос
Добавлено: 17 май 2006, 17:22
vg
aissp писал(а):А метрика на пространстве то задана? Типа возьмем два больных у одного понос и желтуха, у второго типа геморой и триппер. К кому ближе больной у которого диабет и склероз? Мне просто интересно (честно гря ужасно) откуда растут хвосты етой задачи
Положим задана, так что можно определить "расстояние" от точки до заданной в n-мерном пространстве. При большом чиcле точек и большой размерности - может CPU сгореть?
ПС. Такое расстояние следует понимать как степень удалённости точки от других. Это не самтиметры.
?
Добавлено: 17 май 2006, 18:09
aissp
Я пока только уточняю формулирвку задачи, без вынесения рецептов и поиса лекарст, мне интересно узнать постановку. Делать предположения чего и как могет сгореть сантиметры ето или другие единицы? Лучше у аффтара спросить
он точно знает из какой области задача, а на дапускать я и сам гораз полные штаны
таким вот полетом
Добавлено: 17 май 2006, 18:54
vg
Мне самому интересно. Как эффективно и просто решить задачу пусть в простейшем случае, для N - "вещественных" измерений и M - точек. Найти n-ближайших соседей, или определить таковых по заданному радиус-вектору. Если вычислять радиус-вектор до каждой точки, чтоб найти n-ближайших соседей случайной точки - это долго.
Поэтому генерируовать точки надо так, чтобы индекс Marmot-това простанства обновлялся при генерации, т. е автоматически.
Добавлено: 17 май 2006, 19:11
Stanislav
vg писал(а):... Marmot-това простанства .....
А красиво получилось! Marmot-тово простанство - звучит!!!
Да их вроде
Добавлено: 17 май 2006, 19:32
aissp
много всяких R tree brep three kdb tree кирвая гилбьерта/ я сталкивался тока с R tree насколкьо я знаю успешных проектов использование R деревбев для измерений больше трех не было. Ну и спич идет о пространстве равномерно заполненным точками. Поетому честно говоря ответить мне нечегоЮ а вот ответы услышать интересно=)