Приближенный поиск в базах данных на основе метрических деревьев

• Автор: Колесов, Дмитрий Александрович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Казань
• Количество страниц: 148 с. : ил.

1 Приближенный поиск в метрическом пространстве

1.1 Понятие приближенного поиска

1.2 Приближенный поиск в метрических пространствах: обзор основных алгоритмов

1.3 Поиск в метрических пространствах: обобщающая модель

1.4 Выводы

2 Выбор узловых точек, используемых для индексации

2.1 Применение гистограмм расстояний к оценке качества

отдельно взятых узлов

2.2 Применение гистограмм расстояний к оценке качества

набора узлов в целом

2.3 Экспериментальная проверка

2.3.1 Краткое описание эксперимента
2.3.2 Результаты эксперимента
2.4 Выводы
3 Модель приближенного поиска в БД
3.1 Отображение БД в координатное пространство
3.2 Индексация пространства для приближенного поиска
3.3 Поиск в БД по нечетким критериям сходства
3.3.1 Основные понятия теории нечетких множеств.
Лингвистическая переменная

3.3.2 Построение лингвистической переменной «схожесть строк»

3.4 Выводы
4 Применение приближенного поиска при идентификации
останков погибших военнослужащих
4.1 Система идентификации останков военнослужащих
4.1.1 Процесс идентификации останков военнослужащих
{> 4.1.2 Исходные данные: анализ на полноту и достоверность
4.1.3 Требования, предъявляемые к информационной системе идентификации останков погибших воинов
4.2 Этап разработки геоинформационной системы
4.2.1 Краткое описание возможностей ГИС
4.2.2 Слои электронной карты для ГИС «Поисковые
экспедиции»
4.2.3 Вопросы конкретной реализации

4.3 Индексация БД, содержащей сведения о погибших
военнослужащих
4.3.1 Выбор полей БД, участвующих в индексации для приближенного поиска
4.3.2 Выбор узлов, используемых при построении
индексного дерева
4.3.3 Пример выполнения запроса пользователя на
приближенный поиск в БД
4.4 Примеры идентификации
4.4.1 Характеристика района работ поисковой экспедиции «Любань»
4.4.2 Примеры идентификации
4.5 Выводы
Заключение

Литература

♦ Приложения
Приложение
Приложение
Приложение

вычислений метрики (суммарное количество этих операций обозначено на графике символом Т).
Рис. 2.8. Оценка среднего времени поиска с использованием индексных деревьев.
Как видно из рисунка, сначала, с увеличением числа узлов, время поиска резко падает, а потом начинает медленно возрастать. Число узлов, при котором достигается минимум, зависит от многих параметров: отношение времени, необходимого для вычисления расстояний на множестве £/ ко времени перехода между вершинами дерева (чем больше отношение, тем больше узлов необходимо); количества элементов во множестве и (чем больше элементов, тем больше узлов); размерности пространства (чем больше размерность, тем больше узлов). На рисунке приведен случай, когда время перехода между вершинами равно времени, которое; необходимо для вычисления расстояний, число элементов равно 25000, а размерность пространства равна двум. При других значениях этих параметров