Методы, алгоритмы и программные средства повышения скорости поиска в базах данных

• Автор: Коротков, Александр Евгеньевич
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Москва
• Количество страниц: 155 с. : ил.

Содержание
Введение

Глава 1. Анализ современных методов доступа к данным .

1.1. Современные методы доступа к данным

1.2. Задача поиска пространственных данных

1.2.1. Введение

1.2.2. Ядерево

1.2.3. Разделение узла в Кдереве

1.3. Задача нечеткого поиска в строковых массивах.

1.3.1. Расстояние Левенштейна

1.3.2. Разложение строки на кграммы.

1.3.3. ГШдерево.
1.4. Выводы по первой главе
Глава 2. Методы ускорения поиска пространственных данных
2.1. Основные понятия и определения
2.2. Анализ вариантов применения угловых разделяющих пар .
2.3. Алгоритм разделения узла Ндерева
2.4. Применение алгоритма разделения узла Ядсрева к
многомерному случаю
2.5. Выводы по второй главе
Глава 3. Методы ускорения нечеткого поиска в наборах строк
3.1. Вычисление расстояния Левенштейна с пороговым значением .
3.1.1. Обозначения и соотношения.
3.1.2. Алгоритм вычисления расстояния Левенштейна с
пороговым значением.
3.2. Применение ЯЕдерева к набору кграмм для поиска по
расстоянию Левенштейна.
3.2.1. Структура данных
3.2.2. Алгоритм фильтрации сигнатур
3.3. Выводы но третьей главе.
Глава 4. Экспериментальная проверка разработанных методов
4.1. Экспериментальная проверка разработанного алгоритма
разделения узла Ядерева.
4.1.1. Наборы данных.
4.1.2. Эксперименты для одномерного случая на
синтетических наборах данных
4.1.3. Эксперименты для многомерного случая на синтетических наборах данных
4.1.4. Эксперименты на реальных данных .
4.2. Экспериментальная проверка алгоритма вычисления расстояния Левен штейна с пороговым значением.
4.2.1. Наборы данных
4.2.2. Методика проведения экспериментов
4.2.3. Результаты.
4.3. Экспериментальная проверка ИГдерева на основе кграмм . .
4.3.1. Наборы данных
4.3.2. Результаты.
4.4. Выводы по четвертой главе
Заключение.
Литература


Ещё одной распространенной структурой данных для хранения многомерных данных является k-d-дерево [6]. K-d-дерево - это бинарное дерево поиска, хранящее точки k-мсриого пространства. Б каждом промежуточном узле, k-d-дерево делит k-мерное пространство на две части при помощи (к-1)-мерной гиперплоскости. Гиперплоскость перпендикулярна одному из к измерений. Существенным недостатком k-d-дерсва является то, что оно не может эффективно работать во внешней памяти, что важно для больших баз данных. B-дсрсво [7] совмещает в себе свойства k-d-дерева и В-дсрева [], обеспечивая эффективную работу во внешней памяти. Grid-файл и его разновидности [1-4, , ] - это структура данных, основанная на применении хеширования к пространственным данным. Grid-файлы разделяют пространство на области (обычно квадратные). Данные о каждой отдельной области хранятся во внешней памяти вместе. Поиск данных, соответствующих определенной области, осуществляется методом хеширования. R-дерево и подобные деревья [8-] лишены недостатков многих вышеперечисленных структур данных, поскольку могут эффективно работать во внешней памяти, и применимы не только к точкам, но и к объектам, обладающим протяженностью. Одной из наиболее распространенных структур данных для решения этих задач является Я-дерево. Основным недостатком Я-дерева является то, что охватывающие прямоугольники его узлов могут пересекаться. Сильная степень этого пересечения приводит к тому, что при поиске нужно сканировать много путей в дереве, в свою очередь это снижает скорость поиска. В настоящей диссертационной работе предлагается новый алгоритм разделения узла для Я-дерева, позволяющий уменьшить степень пересечения охватывающих прямоугольников узлов, тем самым увеличивая скорость поиска. Разработки в области поиска текста ведутся уже достаточно давно, и некоторые способы поиска очень хорошо проработаны. Например, так называемый, словарный поиск, когда текстовый документ разбивается на токены (неделимые единицы, чаще всего слова или устойчивые словосочетания), для которых осуществляется поиск по строгому соответствию. Для решения задачи словарного поиска разработаны многочисленные разновидности инвертированных индексов, то есть индексов, поддерживающих соответствие между токеном и набором содержащих его документов [-]. Не менее актуальной задачей является нечеткий поиск в строковых массивах, представляющий собой, поиск тех строк, которые “похожи” на заданную. Нечеткий поиск в строковых массивах актуален в целом ряде практических задач, таких как: очистка данных, смягчение поисковых запросов и проверка правописания. Вопросы применения методов нечеткого поиска текста в общей схеме поиска информации освещены в работах [-]. Нечеткий поиск в СУБД не стандартизован, а самих мер похожести строк существует несколько [-]. Среди различных мер “похожести” расстояние Левенштейна [] используется наиболее широко, поскольку оно применимо ко многим случаям. Многие математические методы, впоследствии примененные для нечеткого поиска текста, были изначально разработаны для решения задач кодирования сигналов [, , ]. Например, расстояние Левеиштейна изначально было определено для бинарных кодов []. Многие разработки в области нечеткого поиска текстов были изначально выполнены для решения задач вычислительной биологии, а затем перенесены в другие области. Для индексирования в нечетком поиске широко применяются методы, основанные на к-граммах [, ]. И проблема состоит не в том, что для этого в СУБД отсутствуют необходимые интерфейсы, они как правило присутствуют. Для реализации модификации метода доступа или применении метода доступа к новому типа данных или новому поисковому предикату, в большинстве случаев, требуется низкоуровневое программирование, специфичное для конкретной СУБД. В свете вышеизложенного очень важными являются обобщенные структуры данных, которые позволяют разрабатывать модификации методов доступа и их применения к различным типам данных и поисковым предикатам специалистам предметной области, а не специалистам в области низкоуровневого программирования СУБД.