К созданию архитектуры поисковой системы в наборах документов. Горелов С.С. МГУ им. М.В. Ломоносова механико-математический факультет. - презентация

1 К созданию архитектуры поисковой системы в наборах документов. Горелов С.С. МГУ им. М.В. Ломоносова механико-математический факультет.

2 Введение Математическая модель поиска. Архитектура поисковой системы. Примеры применения преложенной архитектуры. Эффективность предложенной архитектуры. Структура доклада

3 Примеры задач

4 Требования к архитектуре Модифицируемость Производительность Масштабируемость Отказоустойчивость Защищенность

5 Будем полагать, что на рассматриваемом уровне абстракции, ни документы, ни запросы ни схемы не обладают какой-либо определенной структурой. При рассмотрении задачи в поставленном ключе возникают следующие вопросы. Что считать документом, запросом и схемой данных. Каким именно образом осуществляется поиск в наборе произвольных документов какие условия необходимы для того чтобы определить понятие поиска не задавая структуры самих документов и запросов, что будет пониматься под понятием индекс. Что необходимо для осуществления оптимизации поиска для документов произвольной структуры при помощи схем документов, и какие свойства от документов, схем и запросов необходимо потребовать для ее осуществления. Модель поиска

6 Основные понятия Определение Документ D элемент множества D. База данных DB конечное множество документов, DB = {D}. Запрос элемент множества Q. Определение Функцией поиска документа, называется отображение Qd : D х Q {0,1}. Если Qd(D, Q) = 1, то это значит, что документ D соответствует запросу Q, и Qd(D, Q) = 0 в противном случае.

7 Иерархические индексы понятия Определение Полагаем, что каждая схема S задает множество документов (соответствующих S), которое обозначим [S]. Множество всех схем обозначим как S и будем считать множеством произвольной природы. Определение Схема S 1 называется более общей чем S 2, если [S 2 ] [S 1 ]. Также будем обозначать это отношение S 1S 2. Определение Индексом I для базы данных D назовем такое дерево схем, что каждая схема является более общей, чем любая из ее дочерних схем.

8 Иерархические индексы поиск Определение Функцией поиска по схеме будем называть отображение Qs : S x Q {0,1}. При этом Qs(S, Q) = 1, если существует такой D, соответствующий S, что Qd(D,S)=1 и Qs(S, Q) = 0, если такого D не существует Алгоритм, позволяющий сокращать время поиска в общем случае. На каждом шаге алгоритма для рассматриваемой вершины S индекса I проверяем соответствие схемы и запроса. Если условие не выполняется, то «отсекаем» рассматриваемую ветвь индекса со всеми соответствующими документами; если нет, то переходим к проверке дочерних схем.

9 Оптимальные индексы. Стоимость. Определение Функция Cost : S x Q R задает сложность вычислений запроса Q по схеме S. Определение Вероятность схемы P{S} есть вероятность события, что найдется документ соответствующий схеме и удовлетворяющий какому-либо запросу. Математическое ожидание стоимости усечения пространства поиска по данному индексу / коротко назовем стоимостью индекса /. Математическое ожидание стоимости равно: M(I) = S I P{ Ŝ}*|S|. Определение Оптимальным индексом будем называть такой индекс / 0, что для любого другого индекса М(I) > М(I 0 ). Стоимость индекса ограничена снизу, таким образом существует inf I M(l).

10 Построение оптимальных индексов Утверждение Для произвольной вершины оптимального индекса ветвь, состоящая из всех её потомков, также является оптимальным индексом. Рассмотрим некоторую вершину индекса и исходящие из нее ребра. Перебираем некоторые разбиения группы схем на две части, с тем, чтобы выбрать наилучшее, исходя из минимальности стоимости индекса после разбиения. Разбиение исходного множества схем осуществляется с целью уменьшить сумму вероятностей схем, при этом, стремясь к тому, что бы сами вероятности как можно меньше отличались друг от друга.

11 Алгоритм 1 построения индекса Строим тривиальный индекс. Множество {S} – вершины ожидающие обработки. На первом шаге добавляем в {S} корневую вершину. Вычисляем расстояния для всех пар схем S i, S k из тривиального индекса. ЦИКЛ пока множество {S} не пусто. Удаляем из множества {S} произвольную схему S. ЦИКЛ по схемам S' j из {S' 1,…,S' M }. Упорядочиваем схемы {S' 1,…,S' M } по расстоянию до S' j. ЦИКЛ по L от 1 до M-1. Строим множество из первых L ближайших к S' j схем. Вычисляем оценку для стоимости индекса после разбиения {S' i,…,S M } на две части: множество L ближайших к S' j схем и множество оставшихся дочерних для S 1 схем. КОНЕЦ ЦИКЛА Выбираем разбиение с минимальной оценкой. Разбиваем дерево индекса на две части. Добавляем в S вершины, которые стали для нее дочерними в {S}. КОНЕЦ ЦИКЛА

12 Алгоритм 2 построения индекса Строим тривиальный индекс. Множество {S} – вершины ожидающие обработки. На первом шаге добавляем в {S} корневую вершину. ЦИКЛ пока множество {S} не пусто. Удаляем из множества {S} произвольную схему S. Выбираем произвольную схему S' j из множества {S' 1,…,S' M }, дочерних для S 1. Выбираем наиболее удаленную от S' j вершину S' k и упорядочиваем все вершины по расстоянию до нее. Делим полученное множество на две части равные по количеству вершин. Разбиваем дерево индекса на две части в соответствии с выбором. Добавляем в S вершины, которые стали для нее дочерними в {S}. КОНЕЦ ЦИКЛА

13 Модель. Компоненты: D,Q,S, вероятностное пространство над Q. Функции: построение схемы по документу - S(D): D->S; вычисление размера схемы - |S|: S->R; отношение на схемах - S 1 >S 2 : SxS->{0,1}; объединение схем - S 1 +S 2 : SxS->S; вычисление вероятности схемы - P{S}: S->R; вычисление запроса на документе - Qd(D,Q): DxQ->{0,1}; вычисление запроса на схеме - Qs(S,Q): SxQ->{0,1}; проверка соответствия документа схеме – S>D: SxD->{0,1}. Свойства: отношения S 1 >S 2, S>D и операция S 1 +S 2 соответствуют некоторому изоморфизму S и подмножества 2 D ; если верно Qs(S,Q)=0, то для любого D из S: Qd(D,S)=0. функции P{S} и |S| соответствуют своим определениям для вероятностного пространства.

14 Архитектура поисковой системы. Компоненты. Интерфейсы компонент. Взаимодействие компонент.

15 Компоненты поисковой системы. Документ Запрос Схема База данных Вероятностное пространство Индекс

16 Модули.

17 Интерфейс взаимодействия с клиентом. создание индекса для базы данных, удаление индекса; поиск в базе данных по запросу; запуск/останов сервера; создание базы данных по каталогу, содержащему документы; удаление базы данных; добавление/удаление документа; вывод описания результатов выполнения запроса для базы данных; вывод описания результатов выполнения запроса для отдельного документа; вывод статистики выполнения запроса на базе данных; вывод описания документа базы; вывод описания запроса для базы данных; вывод описания схемы из индекса; вывод описания индекса базы данных; вывод описания базы данных; вывод описания всех баз данных сервера.

18 Интерфейсы. Документ, схема, запрос. Функции модуля документов: загрузка документа из файла, сохранение документа в файл, вывод документа в виде XML. Функции модуля схем: вывод схемы в виде XML; сохранение схемы в файл; загрузка схемы из файла; Функции модуля запросов: чтение запроса из строки; вывод запроса в виде XML; сохранение запроса в файл; загрузка запроса из файла; выполнение запроса на документе; выполнение запроса на схеме; время исполнения запроса; вывод результатов запроса в виде XML; вывод строки запроса;

19 Деревья поиска В качестве множества данных, по которому идет поиск рассмотрим двоичные упорядоченные деревья, вершинам которых сопоставлены числа. Определение Дерево Т будем называть деревом поиска, если любая вершины левой ветви имеет значения меньшие t, a правой ветви значения большие t. В таком дереве можно обнаружить произвольный ключ -достаточно, начав с корня, двигаться к левому или правому поддереву на основание лишь одного сравнения с ключом текущей вершины. Для оптимального дерево величина средней взвешенной длины пути (M= i=1..n p i *h i ) достигает своего минимума. Здесь h i уровень (длина пути от корня) вершины р i.

20 Компоненты архитектуры для деревьев поиска 1. Компоненты системы: D = N; Q = N; S = множество интервалов натуральных чисел. 2. Функции компонент: построение схемы по документу - S(D): D->S; вычисление размера схемы - |S|: S->R; отношение на схемах - S 1 >S 2 : SxS->{0,1}; объединение схем - S 1 +S 2 : SxS->S; вычисление вероятности схемы - P{S}: S->R; вычисление запроса на документе - Qd(D,Q): DxQ->{0,1}; вычисление запроса на схеме - Qs(S,Q): SxQ->{0,1}; проверка соответствия документа схеме – S>D: SxD->{0,1}.

21 Пример дерева поиска

22 Индексы полуструктурированных документов Зададим множества модели: D=множество OEM документов. Q=множество CRP запросов. S=множество графовых схем. В работах [1,2] доказаны все свойства необходимые для того, чтобы задать модель поиска для описанных случаев. В рамках проведенных в [1,2] исследований был предложен критерий сравнения индексов, основанный на предположении, что запросы являются случайными величинами. Утверждение Математическое ожидание стоимости выполнения запросов на индексе равно: M(I)= P{Ŝ}*|S|.

23 Приложения в области XML данных Компоненты модели: D XML документ. Q XPath запрос. S схема DTD. Функции на этих множествах: Qd(D, Q) = 0 в соответствии со спецификацией DTD и XML. Qs(S, Q) = 0 в случае, когда после перезаписи получен противоречивый XPath запрос. Величина P{S}, напрямую зависит от рассматриваемого вероятностного пространства запросов. В данном конкретном случае не будем определять ее.

24 Приложения в области XML данных Построение схемы по документу - S(D): D->S. Вычисление размера схемы - |S|: S->R. Отношение на схемах - S1>S2: SxS->{0,1}. Объединение схем - S1+S2: SxS->S. Проверка соответствия документа схеме – S>D. Покажем, что выполняются необходимые свойства: По определению функций Qs и Qd, выполняется условие о том, что равенство Qs(S, Q) = 1 верно, если существует D, соответствующий S, и Qd(D,S) = 1. Множество S изоморфно некоторому подмножеству 2 D, по определению S. Множество S замкнуто относительно операций объединения и пересечения схем, так как S представляет собой множество.

25 Эффективность. Оценки сложности алгоритмов. Пусть база данных состоит из N документов, а размер схемы оценивается сверху как |S|. Пусть сложность вычисления |S| оценивается, как C |S|, сложность вычисления P {S} как C P{S}, а сложность вычисления S 1 +S 1 как C S1+S2. (Теорема) Cложность алгоритма 1 построения индекса для поиска в наборе документов можно оценить сверху как O(NC |S| +N 2 (C S1+S2 +C P{S} )+N 3 ln(N)). (Теорема) Cложность алгоритма 2 построения индекса для поиска в наборе документов можно оценить сверху как O((C S1+S2 +C P{S} )Nln(N)).

26 Эффективность Предположим, что мощность множества запросов равна M, все запросы равновероятны, при этом все результаты их вычисления различаются между собой. (Предложение) Не существует индекса, стоимость которого меньше ln 2 (M). (Предложение) Существует алгоритм поиска, сложность которого O(ln(M)). Схема доказательства: Рассмотрим множество результатов поиска их количество M. => Результат однозначно задается последовательностью нулей и единиц - результатов проверок запроса на схемах индекса (этот процесс детерминирован).