Введение
ГЛАВА 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
