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

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

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

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

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

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

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

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

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

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

Алгоритм 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}. КОНЕЦ ЦИКЛА

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

Модель. Компоненты: 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| соответствуют своим определениям для вероятностного пространства.

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

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

Модули.

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

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

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

Компоненты архитектуры для деревьев поиска 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}.

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

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

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

Приложения в области 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 представляет собой множество.

Эффективность. Оценки сложности алгоритмов. Пусть база данных состоит из 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)).

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