Last_AlienКак Вы относитесь к оптимальным бинарным деревьям поиска и построению системы на их основе?Деревья - это хорошо. :)

Last_AlienДля примера пересечения 2млн.записей с атрибутом 1 и 10тыс.записей с атрибутом 2 и их пересечением в 100 записей, можно реализовать систему, поднимающую с диска максимум 122 записи при условии хранения значений атрибутов в самих записях. Увеличение кол-ва записей с атрибутами при том же их пересечении в 100 раз приведет к росту необходимой выборки до 138 записей.Учитываете ли Вы тот факт, что по условиям задачи у нас не два атрибута, заранее известных, для которых мы можем построить одно дерево (или два пересекающихся дерева), а 1000 атрибутов, и мы не знаем заранее, какие именно из них потребуются пользователю в запросе...
Один пользователь возьмет из этой тысячи своих два атрибута, другой - два, три или сразу пять других. Поэтому просто обычное дерево или тривиальное решение под два конкретных атрибута нам не подходит. Я не в курсе - возможно у Вас есть решение, не завязанное на количество атрибутов, но из Вашего объяснения это не ясно.
Вы слышали о такой структуре данных: k-d Tree? Она на каждом шаге построения дерева делит пространство по какому-то одному измерению. И это позволяет быстро локализоваться в пространстве, даже если оно многомерное. Однако, эта структура перестает эффективно работать при очень большой размерности пространства и она очень плохо работает с бинарными атрибутами, ведь их можно поделить только один раз.
И главное - я не видел ни одного адаптивного и при этом гарантировано логарифмического варианта структуры данных, основанной на идее k-d дерева. :( А динамическое добавление (изменение) информации требуется по условиям задачи.

Dimitry SibiryakovНа практике это "переменное количество" на счет "раз" сворачивается в фиксированное, а данные уплотняются. Ну и дальше, как и сказал Последний Алиен, в ход идут оптимальные деревья и битовые маски.Снижение размерности - хорошая идея, которую часто обсуждают в статьях, но здесь нужно локальное снижение размерности, так как в разных областях общего 1000-мерного пространства есть свои и совсем разные гиперкубы, в которые упакованы не все, но многие точки этой области.
Уверяю Вас, если именно для ВСЕХ записей как-то попытаться снизить размерность одним общим способом сразу с 1000 и до разумно маленькой величины - то это породит кучу очень медленных поисков на пользовательских запросах. Данные неоднородны, хотя они и не случайны (поэтому говорить о снижении размерности как о методе можно).
Если у Вас есть идеи именно по адаптивному алгоритму, который бы сам снижал размерность для разных групп точек, делая это по-разному в разных областях простанства - что же, буду рад услышать, если согласны поделится идеями. :)

antandПожалуйста, ну очень Вас прошу, приведите хотя бы краткую постановку задачи с примерами и подайте ее людям для обсуждения. Ну, если не хотите ваших страшных тайн открывать, на которых Вы деньги будете зарабатывать на миллионах пользователей, приведите пример из другой области.Еще раз привожу пример.
----------------------------------------------------------------------
Для начала у нас есть база данных, в которой каждая запись содержит всего три атрибута - "тип товара", "язык" и "город". Тип товара может быть, например, "книга", "фильм", "песня" или, например, "атомобиль". Для медиа-продукции второй атрибут, "язык", говорит нам, на каком языке издана книга, какой язык в переводе фильма и т.п. Третий атрибут - это город, где этот товар выставлен на продажу.
У нас есть 100 миллионов записей о товарах. Из них:
- 2 миллиона записей относятся к городу "Нью-Йорк",
- 100 тысяч разных записей имеют отношение к русскому языку,
- 10 тысяч записей имеют тип "книга".
Но всего-навсего 100 книг на русском языке продаются в Нью-Йорке, а остальные - нет. Их и хочет найти наш пользователь.
Задача тривиальная, если мы заранее, зная специфику пользовательских запросов специально возьмем и построим в какой-нибудь существующей системе индекс по сочетанию полей {"тип товара", "язык", "город"}.
А теперь переходим к полной постановке задачи - снимаем ограничение на количество атрибутов. Этих атрибутов - около тысячи. Причем они добавляются в процессе работы системы, время от времени. И мы не знаем заранее, КАКИЕ именно запросы будут интересны пользователю. У нас очень много пользователей с разными интересами и каждый из них ищет что-то свое, выбирая произвольные атрибуты из 1000 доступных...
----------------------------------------------------------------------
Что нам предлагают коммерческие СУБД в такой ситуации? В лучшем случае они нам предлагают построить индексы по каждому из атрибутов в отдельности (или индекс по паре {ID атрибута, значение}).
И затем они будут оъединять списки или битовые маски, выполняя сложный запрос, включающий больше одного атрибута.
В данном примере они возьмут самый короткий список - список книг (10 тысяч идентификаторов записей в базе) и начнут проверять, присутствуют ли эти же ID записей в списке русскоязычных товаров (100 тысяч элементов) и в списке продающихся в Нью-Йорке (2 миллиона элементов). Как именно это делается - слиянием ли списков, или пересечением битмапов - не важно.
В любом случае это очень-очень медленная работа ПО СРАВНЕНИЮ С ИТОГАМИ - со 100 результирующими записями.
Так происходит потому, что не зная заранее, по каким сочетаниям атрибутов будет искать пользователь, они вынуждены плясать от ОТДЕЛЬНЫХ атрибутов.
----------------------------------------------------------------------
Нужен же "пространственный" индекс, который даже в 1000-мерном пространстве быстро найдет пересечение и поднимет в память не намного больше данных, чем 100 результирующих записей. Он считает больше - чудес же не бывает, но не намного...
Однако "стандартные" виды таких индексов 1). отсутствуют практически во всех коммерческих СУБД (кроме Postgress?) 2). не рассчитаны на пространства большой размерности 3). не рассчитаны на некоторые виды атрибутов, например, на бинарные.
И как я понял за последние 5 лет никаких сдвигов в этой области в коммерческих СУБД не произошло и не наметилось. Значит нужно искать свое решение. Не так ли?

Мимопроходящийа она всё не стоит и не стоит...Мимопроходящий, когда же ты наконец пройдешь мимо? Или сложности с выбором направления движения?

miksoft sysprgИ не предлагайте решения по сведению 1000-мерного пространства к двумерному через тривиальную укладку в две таблицы.А вы предлагаете хранить Терабайты пустоты?Нет, даже если хранить по столбцам, как предлагают в Sybase IQ, то этого не будет. Только индексации пространственной у них все равно при этом нет, к сожалению - поэтому решив проблему не хранения пустоты и динамического добавления столбцов, они увы не решают проблему быстроты поиска (хотя делают ad hoc поиск быстрее обычных СУБД, как они утверждают иногда в десятки и сотни раз быстрее).

miksoftТаки объясните, пожалуйста, чем именно не нравится такой метод?"Физикой" процесса выполнения запроса. Возьмем мой пример, который приводился здесь. Выполняя поиск в предложенной Вами базе, ядро классической СУБД построит сначала список записей по "самому короткому" значению - список всех книг (10 тысяч элементов). Это компактная маленькая структура. Но затем они объединят его уже с более крупным и менее компактным списком записей, для которых "язык" = "русский" (100 тысяч элементов). Как именно они это сделают - не важно. Тут уже много работы, но это еще не самое страшное. У них останется, скажем, 1000 идентификаторов записей (книг на русском языке). Условно так скажем целых чисел, равномерно размазанных по числовой оси на интервале [0; 10^8]. И вот теперь они возьмут последний список из 2 миллионов элементов и начнут его сливать с этим коротким из 1000... Тут-то все и накроется (по быстродействию). А у нас в параллель идут десятки тысяч и сотни тысяч таких запросов (если Вам не нравится моя цифра в миллион).

shuklin sysprg И вот теперь они возьмут последний список из 2 миллионов элементов , увидят что многовато будет (для этого ведется статистика) и сделают full scan по 1000 записей.Да, согласен - может быть и так. И так как именно пространственную локализацию при хранении записей они не учитывают (записи упорядочены в лучшем случае по первичному ключу), то эти 1000 записей окажутся равномерно раскиданными по всем нодам кластера (или по всему диску на одной машине) и эта выборка будет очень медленной.

shuklinВащето ваша задача решается за O(1) но это O в практических случаях скорее всего окажеться больше чем обычные O(NlnN)Каким образом?

ВыбегаллоВ силу своей архитектуры Sybase IQ не хранит пустоту, очень быстро обрабатывает ad-hoc запросы, в том числе звездообразные, допускает несколько индексов на одну колонку и поддерживает до 45,000 колонок в таблице ("There may be performance penalties with more than 10,000 columns in a table"). Позволяет работать в кластере с shared disk архитектурой. Достаточно неплохое решение для данной задачи.Согласен, что возможно это лучшее решение из стандартных (судя по описаниям на сайте).

ВыбегаллоДенормализация - вот что вас спасет. Сколько может быть атрибутов у одного товара? ну десять, ну двадцать, ну тысяча.Если говорить об этом примере с товарами - то у каждого конкретного товара действительно будет мало атрибутов - обычно два-три десятка, ну пара сотен от силы... Только у разных товаров - эти атрибуты разные. Зачастую они разные даже в одной группе по классификации, из-за многообразия мира и из-за неполноты информации. И многие из атрибутов (не все, конечно) характерны для разных групп товаров - они общие семантически. А значит, пользователь может захотеть поискать по ним. Это я к тому, что выделить особенно важные характеристики (кроме нескольких общих) или предсказать заранее основные варианты поиска в общем случае не удастся, как и сократить число атрибутов.

ВыбегаллоЗаведите таблицу товаров, с тысячей полей для аттрибутов, и специальную таблицу переполнения для того 0.00001 % товаров с более чем 1000 атрибутов. У клиентов хранится описатель товаров, в котором для каждого товара прописаны возможные аттрибуты и колонки, в которых их искать - чтобы не было запросов вида "col100=12345 OR col101 = 12345 OR ..."Что это даст-то мне с точки зрения более умной индексации? Все равно дальше будут построены индексы только по отдельным колонкам и еще по паре десятков самых типовых сочетаний, которые я угадаю заранее, логически поразмыслив над проблемной областью задачи.
Но затем многие пользователи начнут свою работу по добыче полезных для себя редких сочетаний данных подавая заранее не предсказанные мной запросы (часто простые, но не продуманные заранее - это невозможно) и база данных начнет объединять списки перелопачивая "весь диск" или все ноды в кластере.