Анализ и разработка индекса для поиска последовательностей элементов произвольного типа по их фрагментам в реляционных базах данных

• Автор: Чернов, Андрей Фёдорович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Санкт-Петербург
• Количество страниц: 156 с. : ил.

ОГЛАВЛЕНИЕ

Список сокращений

ВВЕДЕНИЕ
ГЛАВА 1. Постановка задач исследования. Анализ способов индексации данных. Выбор структур и алгоритмов

1.1 Постановка решаемых прикладных задач

1.1.1 Задача поиска по фрагменту в числовых массивах

1.1.2 Задача текстового поиска по подстроке

1.2 Анализ способов индексации данных и выбор типа индекса для последовательностей элементов

1.2.1 Индексы на основе битовых карт

1.2.2 Hash-индексы

1.2.3 Индексы на основе В-деревьев
1.2.4 Индексы на основе В+-деревьев
1.2.5 Индексы на основе суффиксных структур данных
1.2.6 Индексы на основе R-деревьев
1.2.7 Индексы на основе RD-деревьев
1.2.8 Выбор структуры индекса для индексации последовательностей
1.3 Постановка задач дальнейшего исследования
Выводы по главе
ГЛАВА 2. Разработка модификации структуры RD-деревьев и эффективных алгоритмов поиска с ней
2.1 Асимптотический анализ алгоритмов работы с RD-деревом
2.1.1 Анализ сложности поиска фрагмента в последовательностях по RD-дереву для среднего случая
2.2 Анализ причин «ложных попаданий» при поиске по RD-дереву

2.3 Математическая оценка количества «ложных попаданий» при поиске
по RD-дереву
2.3.1 Вычисление количества комбинаций последовательностей с повторяющимися элементами
2.3.2 Оценка количества «ложных попаданий» при поиске по RD-
дереву
2.4 Модификация структуры RD-дерева для минимизации «ложных попаданий»
2.4.1 Этап 1: добавление в индекс информации о количестве одинаковых элементов в последовательностях
2.4.2 Этап 2: добавление в индекс признаков повторения элементов
подряд в последовательностях
2.4.3 Этап 3: использование разбиения последовательностей для учета порядка расположения элементов
Выводы по главе
ГЛАВА 3. Выбор параметров алгоритмов построения и использования RD-деревьев. Экспериментальная проверка эффективности
3.1 Экспериментальная проверка эффективности поиска с
использованием модифицированных RD-деревьев
3.1.1 Используемые средства для проверки эффективности
3.1.2 Оценка количества «ложных попаданий» при поиске на
случайных данных
3.1.3 Результаты экспериментальной проверки эффективности поиска
3.1.4 Оценка зависимости эффективности поиска от размера БД
3.2 Доработка алгоритма построения RD-дерева для эффективности разбиения последовательностей на фреймы
3.2.1 Разработка алгоритма анализа данных для формирования актуальных разделителей фреймов для содержимого БД
3.2.2 Экспериментальная проверка корректности формирования актуальных разделителей фреймов
3.2.3 Экспериментальная проверка эффективности поиска с использованием доработанного алгоритма построения ЯВ-дерева
3.3 Оценка степени применимости выполненной модификации ЯВ-деревьев к различным искомым данным
3.4 Оценка влияния выполненной модификации ЯВ-деревьев на время построения индекса
3.4.1 Оценка зависимости времени построения от размера БД
Выводы по главе
ГЛАВА 4. Применение полученных результатов для практических задач
4.1 Применение модифицированных ЯВ-деревьев для поиска по
фрагменту в числовых массивах
4.2 Применение модифицированных ЯВ-деревьев для текстового поиска
по подстроке
4.2.1 Применение модифицированных ЯВ-деревьев полнотекстового поиска с использованием хеширования слов
4.3 Реализация индекса на основе модифицированных ЯВ-деревьев для СУБД Роз1вгеБдБ
4.3.1 Выбор встроенного в СУБД индекса для его модификации
4.3.2 Доработка операторов сравнения числовых массивов для учета порядка элементов
4.3.3 Модификация структуры индекса и алгоритмов работы с ним
4.3.4 Использование сигнатур переменной длины в узлах ЯВ-дерева
4.3.5 Анализ экспериментальных результатов
Выводы по главе
ЗАКЛЮЧЕНИЕ

отсортированные в лексикографическом порядке. Например, для строки «banana» суффиксный массив равен {6,4,2,1,5,3} (лексикографически упорядоченные суффиксы: «а», «апа», «апапа», «banana», «па», «папа»). Элемент массива с индексом і выражает индекс суффикса, который будет i-ым в лексикографическом порядке среди всех суффиксов строки [14].
Суффиксный массив представляет собой компактное представление суффиксного дерева. Существуют алгоритмы построения суффиксных массивов на основе суффиксного дерева путем его обхода в глубину. Однако, они имеют мало практического смысла, так как затраты памяти на построение суффиксного дерева значительно больше затрат для хранения суффиксных массивов [14]. Область же задач, решаемых при помощи суффиксных деревьев, больше чем у суффиксных массивов [14].
Для построения индекса на основе суффиксных массивов для столбца таблицы БД (для этого используются обобщенные суффиксные деревья) в диссертационной работе Айткулова П. Г. [14] предлагается использовать одну общую строку для всех индексируемых строк, как их конкатенацию, но разделенную уникальными метаданными и стоп-символами. Добавление новой строки происходит в конец при помощи разработанного в той же работе алгоритма блочного построения суффиксного массива.
В работе Айткулова П. Г. удалось добиться следующих ассимптотических характеристик для суффиксных массивов. Временная сложность построения есть 0(n-log2(n)), поиска подстроки - 0(т + log(n)), где п - длина текста, т - длина подстроки. Требования к памяти неизменны — О(п).
Достоинства суффиксных структур данных
1. Применимость для широкого круга задач текстового поиска.
2. Высокая эффективность поиска строк (последовательностей символов) с логарифмической асимптотикой.