Введение
Глава 1. Анализ современных методов доступа к данным 10
1.1. Современные методы доступа к данным 10
1.2. Задача поиска пространственных данных
1.2.1. Введение 14
1.2.2. R-дерево 17
1.2.3. Разделение узла в R-дереве 26
1.3. Задача нечеткого поиска в строковых массивах 34
1.3.1. Расстояние Левенштейна 36
1.3.2. Разложение строки на k-граммы 41
1.3.3. RD-дерево 42
1.4. Выводы по первой главе 48
Глава 2. Методы ускорения поиска пространственных данных 50
2.1. Основные понятия и определения 50
2.2. Анализ вариантов применения угловых разделяющих пар 52
2.3. Алгоритм разделения узла R-дерева 57
2.4. Применение алгоритма разделения узла R-дерева к многомерному случаю 63
2.5. Выводы по второй главе 67
Глава 3. Методы ускорения нечеткого поиска в наборах строк 68
3.1. Вычисление расстояния Левенштейна с пороговым значением 68
3.1.1. Обозначения и соотношения 69
3.1.2. Алгоритм вычисления расстояния Левенштейна с пороговым значением 77
3.2. Применение RD-дерева к набору k-грамм для поиска по расстоянию Левенштейна 81
3.2.1. Структура данных 81
3.2.2. Алгоритм фильтрации сигнатур 83
3.3. Выводы по третьей главе 86
Глава 4. Экспериментальная проверка разработанных методов 88
4.1. Экспериментальная проверка разработанного алгоритма разделения узла R-дерева 90
4.1.1. Наборы данных 90
4.1.2. Эксперименты для одномерного случая на синтетических наборах данных з
4.1.3. Эксперименты для многомерного случая на синтетических наборах данных 94
4.1.4. Эксперименты на реальных данных 102
4.2. Экспериментальная проверка алгоритма вычисления расстояния Левеиштейна с пороговым значением 103
4.2.1. Наборы данных 103
4.2.2. Методика проведения экспериментов 104
4.2.3. Результаты 104
4.3. Экспериментальная проверка RD-дерева на основе k-грамм 108
4.3.1. Наборы данных 108
4.3.2. Результаты 108
4.4. Выводы по четвертой главе 114
Заключение 116
Литература
