Содержание к диссертации
Введение
ГЛАВА 1. Постановка задач исследования. Анализ способов индексации данных. Выбор структур и алгоритмов 14
1.1 Постановка решаемых прикладных задач 14
1.1.1 Задача поиска по фрагменту в числовых массивах 14
1.1.2 Задача текстового поиска по подстроке 19
1.2 Анализ способов индексации данных и выбор типа индекса для последовательностей элементов 21
1.2.1 Индексы на основе битовых карт 21
1.2.2 Hash-индексы 24
1.2.3 Индексы на основе B-деревьев 26
1.2.4 Индексы на основе B+-деревьев 30
1.2.5 Индексы на основе суффиксных структур данных 32
1.2.6 Индексы на основе R-деревьев 36
1.2.7 Индексы на основе RD-деревьев 40
1.2.8 Выбор структуры индекса для индексации последовательностей 44
1.3 Постановка задач дальнейшего исследования 47
Выводы по главе 1 50
ГЛАВА 2. Разработка модификации структуры RD-деревьев и эффективных алгоритмов поиска с ней 52
2.1 Асимптотический анализ алгоритмов работы с RD-деревом 52
2.1.1 Анализ сложности поиска фрагмента в последовательностях по RD-дереву для среднего случая 53
2.2 Анализ причин «ложных попаданий» при поиске по RD-дереву
2.3 Математическая оценка количества «ложных попаданий» при поиске по RD-дереву 58
2.3.1 Вычисление количества комбинаций последовательностей с повторяющимися элементами 59
2.3.2 Оценка количества «ложных попаданий» при поиске по RD-дереву 65
2.4 Модификация структуры RD-дерева для минимизации «ложных попаданий» 70
2.4.1 Этап 1: добавление в индекс информации о количестве одинаковых элементов в последовательностях 72
2.4.2 Этап 2: добавление в индекс признаков повторения элементов подряд в последовательностях 77
2.4.3 Этап 3: использование разбиения последовательностей для учета порядка расположения элементов 83
Выводы по главе 2 88
ГЛАВА 3. Выбор параметров алгоритмов построения и использования RD-деревьев. Экспериментальная проверка эффективности 90
3.1 Экспериментальная проверка эффективности поиска с использованием модифицированных RD-деревьев 90
3.1.1 Используемые средства для проверки эффективности 91
3.1.2 Оценка количества «ложных попаданий» при поиске на случайных данных 92
3.1.3 Результаты экспериментальной проверки эффективности поиска 94
3.1.4 Оценка зависимости эффективности поиска от размера БД 100
3.2 Доработка алгоритма построения RD-дерева для эффективности разбиения последовательностей на фреймы 103
3.2.1 Разработка алгоритма анализа данных для формирования актуальных разделителей фреймов для содержимого БД 104
3.2.2 Экспериментальная проверка корректности формирования актуальных разделителей фреймов 110
3.2.3 Экспериментальная проверка эффективности поиска с использованием доработанного алгоритма построения RD-дерева 113
3.3 Оценка степени применимости выполненной модификации RD-деревьев к различным искомым данным 115
3.4 Оценка влияния выполненной модификации RD-деревьев на время построения индекса 119
3.4.1 Оценка зависимости времени построения от размера БД 120
Выводы по главе 3 121
ГЛАВА 4. Применение полученных результатов для практических задач 123
4.1 Применение модифицированных RD-деревьев для поиска по фрагменту в числовых массивах 123
4.2 Применение модифицированных RD-деревьев для текстового поиска по подстроке 126
4.2.1 Применение модифицированных RD-деревьев полнотекстового поиска с использованием хеширования слов 129
4.3 Реализация индекса на основе модифицированных RD-деревьев для СУБД PostgreSQL 131
4.3.1 Выбор встроенного в СУБД индекса для его модификации 131
4.3.2 Доработка операторов сравнения числовых массивов для учета порядка элементов 132
4.3.3 Модификация структуры индекса и алгоритмов работы с ним 134
4.3.4 Использование сигнатур переменной длины в узлах RD-дерева 135
4.3.5 Анализ экспериментальных результатов 138
Выводы по главе 4 144
Заключение 146
Список литературы 148
- Анализ способов индексации данных и выбор типа индекса для последовательностей элементов
- Анализ причин «ложных попаданий» при поиске по RD-дереву
- Оценка количества «ложных попаданий» при поиске на случайных данных
- Применение модифицированных RD-деревьев полнотекстового поиска с использованием хеширования слов
Введение к работе
Актуальность работы. В современном обществе огромную роль играют
информационно-поисковые системы (ИПС). Информационные технологии
проникают во все сферы человеческой деятельности. Постоянное увеличение накопленной информации в базах данных (БД) приводит к росту нагрузки и, как следствие, росту требований к поисковым системам, что подчеркивает актуальность и значимость исследований в области информационного поиска.
Для эффективного поиска в БД необходимо иметь соответствующее математическое и программное обеспечение. Для ускорения поиска или даже для создания возможности его выполнения необходима предварительная обработка данных с целью создания вспомогательных поисковых структур – индексов. Современные индексы базируются на таких поисковых структурах как битовые карты, B- и R-деревья, и их модификации, суффиксные структуры данных и др.
Вопросам проектирования структур данных и алгоритмов для информационного поиска посвящены работы Д. Хеллерстейна, А. Гуттмана, Р. Финкеля, М. Никола и других. Из отечественных публикаций можно выделить работы О. С. Бартунова, Т. Г. Сигаева, И. А. Андрианова, П. Г. Айткулова, Л. М. Бойцова и других. Особенно значимыми для данной диссертации явились работы Д. Хеллерстейна, О. С. Бартунова и Т. Г. Сигаева в области структур данных для информационного поиска.
Среди различных видов поиска важным и востребованным является поиск последовательностей элементов (числовые массивы, строки и т.п.). Наиболее востребованным является поиск таких данных по фрагменту. Подобный поиск поддерживается современными индексами с целым рядом ограничений: не всегда учитывается порядок следования элементов, большие требования к памяти и недостаточно эффективные алгоритмы построения индексов.
Кроме того, удобство/возможность индексации последовательностей элементов часто бывают ограничены по причине нормализации хранимой в БД информации. Однако в последнее время все чаще прибегают к изменению логической структуры БД для ее сознательной денормализации. То есть используется умышленное дублирование данных с целью ускорения поиска. К примеру, имеется БД кредитных договоров в коммерческом банке, по каждому договору в хронологическом порядке выполнено множество операций (выдача кредита, погашение, вынос на просрочку и т.п.). Необходимо ускорить поиск кредитных договоров в запросах типа: «найти все договоры, по которым после выдачи кредита было не менее 2 погашений подряд». Для ускорения и упрощения формулирования (например, на языке SQL) подобных поисковых запросов удобно хранить идентификаторы выполненных по договору операций не в отдельной связанной таблице БД, а в виде числового массива в той же таблице. Для полученных числовых массивов удобно построить индекс, ускоряющий их поиск по фрагменту. Это подчеркивает актуальность поиска последовательностей элементов. Однако базы данных, соответствующие третьей нормальной форме (стандарт де-факто при проектировании БД), не позволяют эффективно выполнить такой поиск даже с использованием индексов.
Подобные задачи поиска востребованы и в других предметных областях: информационные системы учебных заведений, системы сбора статистики и т.п.
Поэтому представляется достаточно актуальной задачей реализация индексного метода доступа (МД) к последовательностям элементов для их поиска по фрагменту.
Целью работы является создание индексного метода доступа к данным для эффективного поиска последовательностей элементов по их фрагменту. При этом в качестве последовательностей могут выступать числовые массивы, текстовые строки, бинарный программный код и др.
Для достижения поставленной цели в диссертации решены следующие задачи:
-
Анализ существующих подходов к построению индексов и выбор наиболее подходящего типа индекса для поиска последовательностей по фрагменту.
-
Модификация выбранной поисковой структуры и алгоритмов для ускорения поиска последовательностей по фрагменту.
-
Разработка программных реализаций модифицированной структуры индекса.
-
Получение экспериментальных данных, сравнение с известными аналогами.
5. Внедрение результатов в деятельность конкретных организаций.
Объектом исследования являются коллекции небольших и средних размеров
(до нескольких десятков гигабайт), содержащие последовательности элементов произвольного типа.
Предметом исследования являются способы организации и алгоритмы работы с индексными структурами для эффективного поиска последовательностей по фрагменту.
Методы исследования. В работе использованы методы теории вероятностей, комбинаторики, теории графов, а также методы анализа алгоритмов.
Научная новизна полученных результатов заключается в следующем:
-
Разработана модификация структуры RD-дерева, предложенной Дж. Хеллерстейном и имеющей недостатки при поиске последовательностей в коллекциях размером несколько гигабайт и выше. В рамках модификации доработана структура внутренних узлов дерева, а также алгоритм поиска, в результате чего достигнуто существенное ускорение поиска последовательностей по фрагменту.
-
Доработан алгоритм построения RD-дерева путем добавления в него этапа анализа индексируемых данных, в результате чего сформированные на данном этапе актуальные для содержимого БД параметры построения индекса приводят к дополнительному ускорению поиска с использованием построенной структуры. Кроме того, доработка алгоритма построения индекса обеспечивает одинаковую высокую эффективность поиска, не зависимую от содержимого БД.
-
Предложен подход для уменьшения размера RD-дерева, в котором вместо сигнатур фиксированной длины применены сигнатуры переменной длины, из которых исключаются неиспользуемые младшие и старшие байты. В результате значительно (до нескольких раз) уменьшен размер индекса.
Практическая значимость. Практическую ценность имеют следующие полученные в диссертации результаты:
-
Разработанный индекс для СУБД PostgreSQL, основанный на модифицированном RD-дереве, применяемый для ускорения поиска числовых последовательностей по фрагменту и представляющий собой программный модуль для расширения СУБД.
-
Методика для ускорения и упрощения формулирования сложных, но достаточно востребованных, поисковых запросов, использующая сознательную денормализацию БД и поиск фрагментов в числовых массивах, тем самым обеспечивающая актуальность применения модифицированных
RD-деревьев для ускорения поиска числовых массивов. 3. Прикладное программное обеспечение (ПО), основанное на разработанных
структурах и алгоритмах, позволяющее значительно ускорить поиск по
сравнению с существующими программными средствами, используемыми для
поиска последовательностей по фрагменту. На защиту выносятся следующие основные результаты и положения:
-
Модификация RD-деревьев, предложенных Дж. Хеллерстейном, и поисковые алгоритмы, использующие ее для существенного ускорения поиска последовательностей по фрагменту.
-
Алгоритм формирования актуальных для содержимого БД параметров построения RD-дерева, используемый при анализе данных на начальном этапе построения индекса и приводящий к дополнительному ускорению поиска, а также обеспечивающий одинаковую высокую эффективность, не зависимую от содержимого БД.
-
Подход к построению RD-дерева, приводящий к значительному (до нескольких раз) уменьшению его размера, использующий в узлах дерева сигнатуры переменной длины, из которых исключаются неиспользуемые младшие и старшие байты.
Апробация работы. Основные результаты работы докладывались и получили положительную оценку на ряде международных, всероссийских и региональных конференций, в том числе: международная научно-практическая конференция «Вопросы образования и науки в XXI веке» (г. Тамбов, 2013 г.), международная научно-практическая конференция «Современное общество, образование и наука» (г. Тамбов, 2013 г.), седьмая международная научно-техническая конференция «Автоматизация и энергосбережение машиностроительного и металлургического производств, технология и надежность машин, приборов и оборудования» (г. Вологда, 2012 г.), всероссийская научная конференция «Молодые исследователи -регионам» (г. Вологда, 2009, 2010, 2011 гг.), научный семинар вологодского регионального отделения Научного совета РАН по методологии искусственного интеллекта (г. Вологда, 2013 г.).
Кроме того, материалы работы использованы в Федеральной целевой программе «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы: «Разработка методов формализации и верификации распределенных информационно-поисковых систем на основе сервис-ориентированной архитектуры».
Достоверность научных положений и результатов работы подтверждается математическими доказательствами и выкладками, результатами практических экспериментов по измерению основных параметров разработанного индекса, в том числе на реальных данных, а также апробацией основных положений работы на международных и всероссийских конференциях.
Реализация и внедрение результатов. Теоретические и практические результаты работы внедрены в программные продукты ЗАО «Эр-Стайл Софтлаб» и в учебный процесс кафедры автоматики и вычислительной техники Вологодского государственного университета:
реализация эффективного поиска по фрагменту в числовых массивах, отражающих хронологию выполнения кредитных операций,
значительное повышение производительности операции проверки банковских
клиентов на причастность к террорестическим организациям,
эффективная по скорости работы реализация поиска программного кода решений студентов в системе дистанционного лабораторного практикума по программированию.
Результаты работы используются в учебном процессе при преподавании курсов «Построение и анализ алгоритмов», «Алгоритмы и структуры данных» и на занятиях научного кружка «Программист».
Публикации. Основное содержание диссертационной работы опубликовано в 13 научных работах, среди которых 3 публикации в ведущих рецензируемых изданиях, рекомендованных ВАК, 1 монография и 9 докладов в материалах международных, всероссийских и региональных конференций.
Структура и объём диссертации. Диссертация состоит из введения, 4 глав, заключения, списка сокращений, библиографического списка и 3 приложений. Работа содержит 156 страниц машинописного текста, включая 49 рисунков и 8 таблиц. Библиографический список включает 65 наименований.
Анализ способов индексации данных и выбор типа индекса для последовательностей элементов
Числовые массивы в роли последовательностей элементов удобно использовать для отражения хронологии каких-либо событий. Это могут быть последовательности состояний, в которых искомые объекты находились на протяжении своего существования, либо последовательности произведенных с объектами операций и т.д. При этом предполагается, что эти состояния/операции объектов имеют числовые идентификаторы, тем самым хронология их изменений технически представляет собой числовую последовательность.
Данная практическая задача направлена на поиск таких числовых последовательностей по фрагменту в коллекциях данных размером до нескольких десятков гигабайт. При этом не накладывается ограничений на статичность данных. На практике представляется достаточно полезным поиск в таких последовательностях по фрагменту, т.е. фактически по части истории объекта. Однако по ряду причин эффективная реализация подобных задач поиска часто бывает невозможной, в первую очередь из-за неприменимости индексов в виду особенностей хранения данных в БД.
Достаточно часто индексы могут быть неприменимы либо недостаточно эффективны по причине нормализации хранимой в БД информации. Нормализация данных впервые была представлена в 1970 году и к настоящему времени очень хорошо и широко документирована [35,41,54]. Нормализация данных – это методика для формирования набора таблиц, которые представляют реальные бизнес-записи в базе данных, что полностью избавляет от дублирования данных в условиях высокой стоимости ресурсов хранения [39]. Разработка нормализации данных была выполнена под влиянием действовавших в то время мощных побудительных причин – дисковое пространство было дефицитным и дорогостоящим [39]. В результате общепринятым подходом стало преобразование бизнес-записей в нормализованное представление для компьютеров (и обратно) [39]. Фактически в сформированном наборе таблиц дублируются лишь значения ключей, связывающих таблицы, а основные элементы данных хранятся ровно один раз. В результате нормализации данных одна бизнес-запись может быть представлена посредством десятков или даже сотен таблиц [39]. Нормализованная схема базы данных – неестественное представление бизнес-записей, очень трудное для понимания бизнес-пользователями и неэффективное для формулировки и обработки аналитических бизнес-запросов. [39]
Такая оптимизированная с точки зрения памяти структура хранения данных очень трудна для понимания и требует специальных механизмов для управления всеми задействованными таблицами, что существенно усложняет формулировку и обработку поисковых запросов.
Рассмотрим актуальный пример, требующий поиска хронологических числовых последовательностей элементов. Имеется БД кредитных договоров в коммерческом банке. По каждому договору в хронологическом порядке выполнено десятки и сотни операций (выдача кредита, погашение, вынос на просрочку и др.). Необходимо ускорить поиск кредитных договоров в запросах типа: «найти все договоры, по которым после выдачи кредита было не менее двух погашений подряд». На рисунке 1.1 приведена схема хранения данных, соответствующая третьей нормальной форме [35,41], которая в настоящее время является стандартом де-факто при проектировании БД.
В данном случае требуемый поисковый запрос «найти все договоры, по которым после выдачи кредита было не менее двух погашений подряд» на языке SQL [61] формулируется сравнительно сложно (см. рисунок 1.2). Современные СУБД не позволяют эффективно выполнить такой поиск даже с использованием индексов. Приходится использовать такие неэффективные по быстродействию SQL-операторы, как IN, EXISTS, а также вложенные запросы. В результате такой поисковый запрос выполняется медленно.
Пример поискового запроса к нормализованным данным За последние несколько десятилетий размеры хранилищ данных многократно выросли, что привело к соответствующему снижению стоимости хранения данных. Более того, благодаря появляющимся новым технологиям и способам хранения данных этот процесс продолжается до сих пор. Таким образом, хранилища данных перестали быть дефицитными.
Анализ причин «ложных попаданий» при поиске по RD-дереву
Пусть имеется RD-дерево, построенное для n последовательностей элементов. Рассматривается низкоселективный поисковый запрос фрагмента, т.е. количество успешных результатов поиска невелико и ограничено константой. Все остальные индексируемые последовательности потенциально могут иметь такие сигнатуры, которые приведут к обращению к ним в результате «ложных попаданий», т.е. лишних спусков по узлам RD-дерева. Таким образом, сложность поиска ограничена сверху количеством «ложных попаданий», которое в свою очередь ограничено количеством узлов дерева.
Узлы RD-дерева, как и R-дерева, соответствуют страницам внешней памяти [43]. Следовательно, переходы между узлами дерева соответствуют обращениям к внешней памяти. Каждый внутренний узел RD-дерева содержит определенное константное количество ссылок на поддеревья, а каждый листовой узел – константное количество ссылок на строки таблицы БД. Поэтому в асимптотике получаем, что количество узлов в дереве составляет O(n), и этой величиной ограничено максимальное количество «ложных попаданий».
Однако вероятность «ложного попадания» P при поиске на реальных данных меньше единицы и равна определенному значению, зависимому от n. Получаем, что асимптотика сложности поиска составляет:
Каждый внутренний узел в RD-дереве при срабатывании в нем условия исключения поддерева из поиска, исключит такое количество «ложных попаданий», которое смогут исключить в сумме все потомки данного узла. Отметим, что для всех этих потомков исключаемое ими количество «ложных попаданий» будет одинаковое в виду сбалансированности RD-дерева по высоте.
Сигнатура каждого узла RD-дерева является неким объединением сигнатур его потомков (побитовое сложение сигнатур, основанных на блюмовских фильтрах). Алгоритмы построения RD-дерева обеспечивают минимальную степень взаимного пересечения сигнатур узлов одного уровня [43], которую можно считать константой. Следовательно, можно допустить, что «вес» сигнатуры узла равен сумме «весов» сигнатур дочерних узлов. Очевидно, что данный «вес» сигнатуры – величина обратная вероятности исключения соответствующего поддерева из поиска.
Учитывая, что количество потомков какого-либо внутреннего узла RD-дерева равно p (порядок дерева), получаем, что срабатывание условия исключения поддерева из поиска с одной стороны в p раз маловероятнее, чем для дочерних узлов, но при этом во столько же раз больше исключает «ложных попаданий». Таким образом, каждый уровень в структуре RD-дерева вносит одинаковый вклад в исключение «ложных попаданий». Следовательно, вероятность ложных попаданий P линейно зависит от количества уровней в RD-дереве (зависимость обратная). Поскольку количество уровней в дереве ограничено величиной O(log(n)), то P будет ограничено обратной величиной:
При анализе структуры индексов на основе RD-деревьев было сказано, что «ложные попадания» при поиске являются следствием коллизий хеширования при построении узлов дерева. В результате чего для различных последовательностей элементов могут быть одинаковые сигнатуры, что приводит к ошибочному чтению узлов дерева, т.е. страниц внешней памяти. Кроме того, для исключения «ложных попаданий» требуются дополнительные чтения страниц внешней памяти для получения сохраненных в БД последовательностей и их сравнения с искомым фрагментом. Таким образом, на существенных объемах данных количество «ложных попаданий» может быть настолько большим, что сделает скорость поиска по индексу неприемлемо низкой.
Проанализируем причины «ложных попаданий» более подробно, учитывая особенности блюмовских фильтров, хранимых в сигнатурах узлов RD-дерева. В сигнатурах каждому значению элементов индексируемых последовательностей соответствует 1 бит – признак наличия элементов с соответствующим значением. Фактически это означает, что последовательности будут иметь различные сигнатуры, только если они различаются составом элементов. Если же состав элементов одинаковый, то сигнатуры последовательностей будут равны, даже если последовательности имеют разное количество элементов и/или различное их расположение. Например, числовые последовательности {1,2,3} и {3,1,2,2,1,3,1} будут иметь одинаковую сигнатуру, в которой установлены биты для значений 1, 2 и 3. Очевидно, что на реальных данных таких «совпадений» будет огромное количество.
Оценка количества «ложных попаданий» при поиске на случайных данных
В данном разделе описан еще один этап в разработке модификации RD-деревьев для устранения второй причины «ложных попаданий» – не учитывается порядок расположения элементов в сигнатурах.
На предыдущем этапе модификации в сигнатуры RD-деревьев был добавлен признак повторения элементов подряд в индексируемых последовательностях. В результате порядок расположения элементов теперь частично учтен в сигнатурах RD-дерева. Однако этого недостаточно, поскольку эффект от выполненного второго этапа модификации проявляется только при поиске фрагментов, содержащих соседние повторения. Подобные поисковые запросы встречаются не так часто, поэтому необходим более точный учет порядка элементов в последовательностях. Решению этой проблемы посвящен третий этап модификации сигнатур RD-деревьев.
На данном этапе для получения дополнительной информации о расположении элементов используется разбиение индексируемых последовательностей на части. Для этого некоторые значения элементов выбираются в качестве разделителей.
Определение 2.3 Фреймы – фрагменты индексируемых последовательностей, используемые для учета порядка расположения элементов. Деление последовательностей на фреймы осуществляется отдельными выбранными значениями элементов – разделителями. Определение 2.4 Граничные элементы - элементы индексируемых последовательностей, являющиеся крайними элементами фреймов, образованных в результате разбиения. При этом разделители фреймов не являются граничными элементами, т.к. не входят в состав фреймов.
В результате разбиения индексируемых последовательностей на фреймы появляется информация о порядке расположения элементов, которая добавляется в сигнатуры узлов RD-дерева. А именно, для каждого значения элементов в соответствующий сигнатурный элемент добавляется признак того, что элементы с данным значением являлись граничными хотя бы раз в отображаемой последовательности. Данная информация делает описание сигнатурами хранимых последовательностей еще более полным, что приводит к снижению количества «ложных попаданий».
Технически в сигнатуры добавляется 1 бит информации в качестве признака наличия граничных элементов для каждого значения, т.е. в каждый сигнатурный элемент. Структура сигнатурного элемента после третьего этапа модификации приведена на рисунке 2.10.
С точки зрения построения сигнатур на основе блюмовских фильтров данная модификация означает добавление третьей хеш-функции. При этом первая хеш-функция, устанавливающая количество, теперь заполняет только 6 младших бит сигнатурного элемента. Вторая хеш-функция, устанавливающая признак повторения подряд, по-прежнему использует старший 7-ой бит. Третья же (новая) хеш-функция устанавливает 6-ой бит сигнатурного элемента, используя его как признак наличия граничных элементов с соответствующим значением.
Таким образом, максимальное учитываемое количество одинаковых элементов в последовательности будет равно 26, т.е. 64. Этого также будет достаточно для индексируемых последовательностей среднего размера (текстовые поля в БД, числовые массивы и т.п.), поскольку так часто элементы в последовательностях на реальных данных не повторяются. При превышении же максимального количества одинаковых элементов фактическое количество «обрезается» до максимально значения (до 63-х, т.к. нумерация с нуля). Таким образом, превышение максимального количества одинаковых элементов просто не будет приносить дальнейшего эффекта для ускорения поиска. Однако вероятность такого превышения достаточно мала.
При внесении таких изменений в структуру сигнатур RD-дерева изменяется алгоритм проверки сигнатур при поиске. В данную проверку добавляется определенная обработка признака граничных элементов. Все достоинства использования предыдущих двух этапов модификации сигнатур сохраняются. Измененный алгоритм проверки включения сигнатур друг в друга, отмеченный в общем алгоритме поиска по RD-дереву в приложении А, приведен на рисунке 2.12.
В результате данная модификация RD-деревьев увеличивает скорость поиска фрагментов с граничными элементами, т.е. фрагментов с фреймами. Например, {162,32,171,165,225} при использовании значения 32 в качестве разделителя (здесь элементы 162 и 171 являются граничными). Из поиска в таких случаях исключаются поддеревья, в сигнатурах которых для какого-либо значения элементов сброшен бит наличия граничных элементов, в то время как в сигнатуре искомого фрагмента этот бит установлен.
Например, для фрагмента {1,1,2,3}, используя в качестве разделителя значение «2», сигнатура будет равна {(1,++2)(2,--1)(3,-+1)}. При поиске такого фрагмента будет исключено из рассмотрения поддерево, имеющее сигнатуру {(1,+-2)(2,--1)(3,-+1)}, хотя все значения элементов там присутствуют не в меньшем количестве, и также элемент «1» повторяется подряд. Дело в том, что элемент «1» в поддереве никогда не располагается на границе фрейма, а в искомом фрагменте располагается. При использовании сигнатур после второго этапа модификации данная сигнатурная проверка была бы пройдена, и в поиск попало бы поддерево, не удовлетворяющее поиску.
Математическая оценка количества «ложных попаданий» после третьего этапа модификации
Выполнить математическую оценку количества «ложных попаданий» при использовании модифицированных сигнатур RD-дерева на третьем этапе представляется затруднительным, так как данное количество напрямую зависит от выбранного набора разделителей фреймов. Ценность такой доработки для эффективности поиска доказывается эмпирически в последующих главах. Кроме того, в третьей главе предлагается доработка алгоритма построения RD-дерева, путем добавления в него этапа анализа индексируемых данных, на котором набор разделителей фреймов будет формироваться автоматически по содержимому БД, обеспечивая высокую эффективность третьего этапа модификации для любого конкретного содержимого БД.
Применение модифицированных RD-деревьев полнотекстового поиска с использованием хеширования слов
Постановка этой задачи приведена в главе 1 (раздел 1.1.1). Данная задача практического применения модифицированных RD-деревьев заключается в ускорении поиска по фрагменту в числовых массивах, которые отражают хронологию каких-либо событий. Посредством числовых массивов могут быть отражены, например, последовательности состояний, в которых искомый объект находился на протяжении своего существования, последовательности производимых объектом (либо с объектом) операций, и т.д. При этом должна быть возможность эти состояния/операции технически представить числовыми массивами. В таких массивах порядок расположения элементов имеет значение. Следовательно, становится возможным применение модифицированных RD-деревьев, разработанных в предыдущих главах, для ускорения поиска объектов по фрагменту их состояний/операций. Если же порядок следования элементов не важен при поиске по фрагменту, то применим только первый этап модификации структуры RD-деревьев.
Модифицированные RD-деревья достаточно компактны, благодаря фиксированному размеру сигнатур, не зависящему от длины индексируемых последовательностей. При этом асимптотика расходования памяти составляет O(n), где n – количество индексируемых последовательностей. Кроме того, RD-деревья обладают быстрыми операциями вставки/обновления с временной сложностью O(log(n)). Поэтому они хорошо применимы для данной практической задачи, которая ориентирована на поиск числовых массивов, которые могут часто обновляться, в коллекциях данных размером до нескольких десятков гигабайт.
Как сказано при постановке задачи в первой главе, достаточно часто применимость индексов для числовых массивов, отражающих хронологические события, бывает невозможной вследствие нормализации данных в реляционных СУБД [35,41,54]. В результате поисковые запросы, аналогичные по смыслу поиску фрагмента в числовых массивах, сложно формулируются и долго выполняются. Для этого, как правило, требуются вложенные запросы и такие SQL операторы, как IN, EXISTS, OR и т.п., которые медленно выполняются на современных СУБД. При использовании денормализованных таблиц БД, содержащих отдельный столбец для хранения числовых массивов, даже полный перебор с поиском по фрагменту часто будет выполняться быстрее, чем вложенные запросы с SQL операторами IN, EXISTS, OR. Использование же индекса на основе модифицированных RD-деревьев по такому столбцу денормализованной таблицы позволит существенно ускорить подобные поисковые запросы.
Для реализации подобных задач поиска разработана специальная методика, использующая сознательную денормализацию логической структуры БД и поиск фрагментов в числовых массивах. Суть данной методики описана при постановке задачи в первой главе, здесь же сформулируем методику более конкретно, используя разработанную модификацию RD-деревьев: 1. Последовательности состояний/операций искомых объектов, хранимые в отдельных связанных таблицах БД, преобразуются в числовые массивы; 2. В таблицу БД, где хранятся искомые объекты, добавляется новый столбец, в котором сохраняются полученные числовые массивы состояний/операций; 3. Для данного столбца таблицы строится индекс на основе модифицированных RD-деревьев, который позволяет эффективно искать объекты по фрагменту истории их состояний/операций.
Данная методика позволяет упростить формулировку и существенно ускорить сложные, но при этом достаточно востребованные поисковые запросы. Тем самым обеспечивается актуальность выполнения поиска фрагментов в числовых массивах, а, следовательно, актуальность применения к такому поиску модифицированных RD- деревьев.
К примеру, в свободно распространяемой СУБД PostgreSQL для решения подобных задач поиска разработан специальный тип данных intarray, представляющий собой целочисленный массив с поддержкой индексного доступа. Далее в этой главе реализован индекс для PostgreSQL, в котором использованы модифицированные БШ-деревья для поиска массивов типа intarray по фрагменту.
