Выполнил: Горелов С.С. Под руководством: с.н.с. Афонин С.А., проф. Васенин В.А. Усечение пространства поиска в полуструктурированных данных при помощи иерархии схем.

Основные понятия Документ – OEM модель. Схема документа – класс документов. Запросы – CRP запросы, регулярные запросы. Иерархия схем – дерево со схемами в вершинах. Стоимость иерархии – характеристика отражающая скорость и точность усечения запросов с помощью иерархии схем. Основная идея усечения пространства поиска при помощи схем: Существует алгоритм проверки по схеме и запросу, что ни один документ, соответствующий этой схеме не дает результата при поиске по данному запросу.

Примеры схемы, документа и запросов

Пример иерархии схем

Проблематика задачи При наличии алгоритма усечения пространства поиска по иерархии схем необходимо предложить критерий сравнения иерархий. Разработать алгоритмы построения иерархии в соответствии с предложенным критерием: –Для базы полуструктурированных документов –Для потока полуструктурированных документов

Критерий построения иерархии Неформальный критерий: «Запросы должны вычисляться за наименьшее количество времени». Два аспекта формализации: 1.Что понимается под «временем»? – стоимость вычислений (количество операций) 2.Что понимается под «наименьшим»? – средняя стоимость выполнения запрос (математическое ожидание стоимости). Основные идеи подхода: Запросы есть случайные величины. Целью осуществления усечения является сокращение математического ожидания стоимости вычисления запросов (сократить среднее время вычисления запросов).

Теория Вероятность схемы P{S}:=P{Q(S)=Ø} Стоимость иерархии Понятия Существует наилучшая иерархия схем, такая, что стоимость любой другой иерархии не меньше, чем у наилучшей. Стоимость иерархии есть сумма (по всем вершинам дерева) произведений весов вершин на сложность перейти к рассмотрению дочерних вершин. Где вес вершины есть вероятность того, что эту вершину придется обрабатывать. Результаты

Интерпретация результатов Усечение пространства поиска при помощи иерархии схем Поиск по равенству при помощи индекса Алгоритмическая сложность продвижения по дереву иерархии зависит от схем Алгоритмическая сложность продвижения по дереву индекса постоянна Сложность поиска в документах оставшихся после усечения зависит от свойств оставшихся документов Результат поиска известен сразу после прохождения индекса и сложность его нахождения не зависит от свойств документа Характеристика скорости усечения M=\Sum Характеристика скорости поиска глубина дерева Сравнительный анализ свойств усечения пространства поиска при помощи иерархии схем и поиска по равенству в реляционной базе при помощи уникального индекса.

Неформальные требования к иерархии Количество схем не должно быть слишком большим с тем, чтобы не тратить много времени на проверку запроса на схемах. Размеры схем так же не должны быть слишком большими по той же причине. Схемы должны объединять в группы похожие в некотором смысле документы.

Построение иерархии схем для полуструктурированной базы данных Алгоритм представляет собой итерационный процесс. На первом шаге процесса: -выделяем группу близких (в определенном смысле) схем, -Строим схему обобщения и добавляем в иерархию как родительскую для объединяемых. На каждом следующем шаге рассматриваем верхний уровень схем и производим с ними описанные выше операции. Общая схема алгоритма: Построение иерархии необходимо осуществлять исходя из свойств локальной минимальности стоимости наилучшей иерархии. Основная идея:

Вероятностное пространство Ограничимся рассмотрением множества элементарных регулярных запросов. Для любого натурального m и элементарного запроса Q существует его приближение на множестве документов с количеством вершин меньше M. Будем рассматривать элементарные запросы, состоящие из слов, длина которых не превосходит наперед заданного M. Вероятность запроса есть произведение вероятностей присутствия (отсутствия ) строк из которых он состоит (которые в нем отсутствуют). вероятность всех последовательностей заданной длины i одинакова и равна ; вероятность последовательности длины i+1 равна ; вероятность появления последовательности, состоящей из одного символа равна. Допущения Структура вероятностного пространства

Составляющие компоненты оценки сложности алгоритма Выделение группы близких схем состоит из: –перебор групп схем (на основе введенного расстояния выделяем групп близких схем) –вычисление оценки стоимости иерархии после объединения группы схем (можно оценить, как ). Построение схемы обобщения состоит из: –нахождение близких вершин (можно оценить, как ) –склеивание найденных вершин (можно оценить, как ). Выделение группы близких схем -- Построение схемы обобщения -- Оценить количество раз, которые придется проделывать вышеописанные операции можно, как N. Оценка сложности для алгоритма построения иерархии по ПБД:

Проблематика: Основной способ составления электронных каталогов и баз данных Интернет-ресурсов – последовательное добавление документов в базу данных Сложность построения иерархии схем после каждого вновь добавленного документа есть Постановка задачи: Имеется конечное множество документов. Из последовательно извлекаются документы и добавляются в базу данных, по которой будет производиться поиск. На каждом шаге необходимо иметь иерархию схем, с помощью которой будет проводиться усечение пространства поиска. Построение иерархии по потоку документов

Общие идеи разработки алгоритма построения иерархии по потоку документов Для документа строится схема и добавляется как дочернюю для какой-нибудь вершины уже существующей иерархии. Части иерархии, не допускающие документ, не имеют с ним ни чего общего и при добавлении документа не изменяются. Вершина иерархии в которую добавляется документ ищется из соображений минимизации стоимости полученной при модификации иерархии. При добавлении документов в одну и ту же ветвь иерархии наступает момент времени, когда эту ветвь необходимо перестраивать.

Критерий переполнения иерархии. Добавленные документы помечаются как «новые». Для каждого «нового» документа, добавленного в схему S рассматривается группа дочерних для S схем. Для «нового» документа рассматриваются подгруппы близких схем, выделенные из определенной выше группы. Вычисляется оценка стоимости для иерархий получаемых после объединения описанных подгрупп. Если стоимость какой-нибудь новой иерархии меньше, чем прежней, то ветвь, соответствующая вершине S считается переполненной.

Оценки сложностей полученных алгоритмов Сложность построения иерархии по ПБД равна, где K – кол-во документов в базе. Обозначим: –алгоритм добавления документа в иерархию – 1; –алгоритм проверки критерия переполнения – 2; –алгоритм построения иерархии для переполненной ветви - 3; Сложность алгоритмов, запущенных для вершины иерархии с K дочерними схемами: 1 -, 2 -, 3 -. Суммарный вклад в сложность построения иерархии посредством добавления документов: 1 -, 2 -, 3 -. В сумме, если принять K за константу, получим, что сложность построения иерархии равна, что на порядок (по N) меньше сложности построения иерархии по всей ПБД сразу.

Сравнение стоимостей построенных иерархий. По оси Х отложено количество документов. По оси У стоимость иерархии деленная на количество документов в базе. | Синим отмечены графики, соответствующие алгоритму построения иерархии схем по всей ПБД. | Красным отмечены графики, соответствующие алгоритму построения иерархии схем по потоку документов. Правый график – база сгенерированная по 4 схемам. Левый график – база эмитентов c

Сравнение времени построения иерархий. По оси Х отложено количество документов. По оси У время построения иерархии деленное на количество документов в базе. | Синим отмечены графики, соответствующие алгоритму построения иерархии схем по всей ПБД. | Красным отмечены графики, соответствующие алгоритму построения иерархии схем по потоку документов. Правый график – база сгенерированная по 4 схемам. Левый график – база эмитентов c

Примеры иерархий, полученных в результате выполнения алгоритма построения иерархии. Пример схемы из иерархии.