Введение
Глава 1. Обзор существующих методов пространственного индексирования 16
1.1 Классификация методов пространственного индексирования 16
1.2 Композиция объектов 20
1.3 Декомпозиция пространства 31
1.4 Предварительные выводы 40
Глава 2. Регулярные октальные деревья 42
2.1 Пространственная декомпозиция на основе октальных деревьев 43
2.2 Теоретический анализ сложности метода декомпозиции
2.2.1 Анализ сложности построения регулярного октального дерева 50
2.2.2 Анализ сложности определения столкновений 53
2.2.3 Анализ сложности выборки объектов по заданной области 60
2.2.4 Анализ сложности поиска ближайших соседей 65
Глава 3. Схемы пространственно-временного индексирования 69
3.1 Альтернативные схемы пространственно-временного индексирования 72
3.1.1 Схема А. Временно-пространственная декомпозиция 74
3.1.2 Схема В. Событийное индексирование 76
3.1.3 Схема С. Пространственно-временная декомпозиция 77
3.2 Анализ сложности разрешения запросов с использованием различных схем пространственно-временного индексирования 78
3.2.1 Развертывание пространственно-временного индекса 79
3.2.2 Реконструкция сцены на заданный момент времени 79
3.2.3 Поиск объектов в области видимости 81
3.2.4 Анимационный запрос 81
3.3 Сравнительный анализ 82
Глава 4. Методы индексирования сложных иерархически организованных пространственных данных 84
4.1 Организация пространственных сцен 84
4.2 Проблемы исполнения запросов к иерархическим данным 84
4.3 Комбинированный метод индексирования 88
4.4 Модельный набор иерархически организованных данных 92
4.5 Сложность развертывания комбинированного индекса 92
4.6 Оценка затрат на хранение комбинированного индекса 95
Глава 5. Вычислительные эксперименты 97
5.1 Серия экспериментов с октальными структурами 97
5.2 Серия экспериментов с комбинированными структурами 103
5.3 Результаты экспериментов с реальными наборами данных 105
5.4 Результаты апробации и внедрения предложенных методов 111
Заключение 115
Список литературы
