Перспективные методы индексирования пространственно-временных данных

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

Оглавление
Введение
Актуальность исследования
Объем и структура работы
Глава 1. Обзор существующих методов пространственного индексирования
1.1 Классификация методов пространственного индексирования
1.2 Композиция объектов
1.3 Декомпозиция пространства
1.4 Предварительные выводы
Глава 2. Регулярные октальные деревья
2.1 Пространственная декомпозиция на основе октальных деревьев
2.2 Теоретический анализ сложности метода декомпозиции
2.2.1 Анализ сложности построения регулярного октального дерева
2.2.2 Анализ сложности определения столкновений
2.2.3 Анализ сложности выборки объектов по заданной области
2.2.4 Анализ сложности поиска ближайших соседей
Глава 3. Схемы пространственно-временного индексирования
3.1 Альтернативные схемы пространственно-временного индексирования
3.1.1 Схема А. Временно-пространственная декомпозиция
3.1.2 Схема В. Событийное индексирование
3.1.3 Схема С. Пространственно-временная декомпозиция
3.2 Анализ сложности разрешения запросов с использованием различных схем пространственно-временного индексирования
3.2.1 Развертывание пространственно-временного индекса
3.2.2 Реконструкция сцены на заданный момент времени
3.2.3 Поиск объектов в области видимости
3.2.4 Анимационный запрос
3.3 Сравнительный анализ
Глава 4. Методы индексирования сложных иерархически организованных пространственных данных
4.1 Организация пространственных сцен
4.2 Проблемы исполнения запросов к иерархическим данным

4.3 Комбинированный метод индексирования
4.4 Модельный набор иерархически организованных данных
4.5 Сложность развертывания комбинированного индекса
4.6 Оценка затрат на хранение комбинированного индекса
Глава 5. Вычислительные эксперименты
5.1 Серия экспериментов с октальными структурами
5.2 Серия экспериментов с комбинированными структурами
5.3 Результаты экспериментов с реальными наборами данных
5.4 Результаты апробации и внедрения предложенных методов
Заключение
Список литературы

Введение
Актуальность исследования
Работа посвящена актуальной теме разработки методов индексирования данных для современных программных систем моделирования динамических сцен. Системы находят применение в таких областях как виртуальная и дополненная реальность, анимация, компьютерные игры, автоматизированное проектирование и производство, робототехника, комплексная инженерия, планирование и управление проектами. Функции подобных систем предполагают развитый набор операций, обеспечивающих не только растеризацию сцен, но и композицию, навигацию, динамическую реконструкцию событий и пространственный анализ. Однако высокая вычислительная сложность операций оказывается ключевым фактором, препятствующим использованию существующих систем при моделировании масштабных сцен и решении актуальных прикладных задач высокой размерности.
Популярные СУБД общего назначения, такие как Oracle, IBM DB2, Microsoft SQL Server, предоставляют дополнительные средства пространственного индексирования многомерных данных. Однако набор методов, как правило, ограничен сбалансированными ветвистыми деревьями, хранимыми во внешней памяти. К методам этого семейства относятся обобщения В-деревьев, предложенные в работах [1,2] (Kamel, I.; Faloutsos, C.), а также различные варианты R-деревьев, описанные в работах [3] (Guttman. Л.), [4] (Sellis, Т.; Roussopoulos, N.; Faloutsos, C.), [5] (Beckmann, N.; Kriegei, H. P.; Schneider, R.; Seeger, В.). Данные методы требуют значительных вычислений при построении и обновлении индексов и поэтому их применение к динамическим данным крайне ограничено.
Методы компьютерной графики, в частности, методы отсечений на основе k-D деревьев [6] (Bentley, J.L.), октальных деревьев [7] (Kcdem, G.), XY-деревьев [8] (Nagy, G.; Wagle, S.), puzzlc-деревьев [9] (Dengel, A.), treemap-структур [10] (Shneiderman, В.) в основном используются для растеризации двумерных и трехмерных данных, однако не обеспечивают реализацию перечисленных выше функций при работе со сложно структурированными данными.
В связи с этим актуальной представляется разработка и исследование новых методов индексирования данных, учитывающих особенности приложений моделирования динамических сцен.
Целыо работы являлась разработка и исследование новых перспективных методов индексирования многомерных данных, обеспечивающих эффективное решение задач

неоднозначностью приписывания объектов, лежащих на секущих плоскостях, тому или иному дочернему октанту. Существует несколько альтернатив. В случае приписывания объекта нескольким октантам возрастают расходы на хранение избыточных ссылок, а также дополнительные вершины подвергаются анализу в ходе выполнения типовых запросов.
Другой альтернативой является возможность ассоциировать такие объекты непосредственно с разбиваемой вершиной. В этом случае каждый объект оказывается ассоциированным только с одним октантом, что упрощает реализацию операций добавления и удаления объектов. Данный способ применяется, в частности, в структуре со строгой многоуровневой локализацией, известной в литературе как MX-CIF octree [7]. Однако при ее использовании существует вероятность, что большая часть объектов сцены попадет на секущие плоскости верхних октантов и окажется приписанной им. В этом случае дерево вырождается и его дальнейшее использование для разрешения пространственных запросов теряет смысл. Проблема особенно усугубляется для объектов, соразмерных габаритам единичных октантов, но локализующихся на верхних уровнях дерева.
В работах [79, 80, 81] данная проблема решается путем пропорционального увеличения габаритов каждого октанта в р > 0 раз вдоль каждой из осей. Параметр р выбирается, исходя из размеров объектов, подлежащих более строгой локализации. Недостатком данного метода является перекрытие октантов и необходимость анализа большего числа вершин при типовых запросах (этот аспект довольно близок проблеме пространственного перекрытия в методах кластеризации объектов). Для преодоления этого недостатка в работе [81] было предложено смещать положение плоскостей разбиения относительно центра разбиваемого октанта на четверть его размера вдоль каждой из осей. В этом случае исключается пересечение дочерних октантов, однако увеличивается число дочерних ячеек. Можно показать, что при выборе параметра /7 = 1/2 любой объект сцены локализуется в ячейке, габариты которой не превышают размеры объекта более чем в 4 раза. Несмотря на увеличение числа вершин и усложненный пространственный анализ, данный метод хорошо компенсирует недостатки классических октальных деревьев, поскольку обеспечивает точную локализацию объектов и позволяет установить однозначное соответствие объектов вершинам октального дерева.
На рисунках 9а-9д приведены псевдокоды алгоритмов для выполнения основных пространственных запросов к рассмотренным в этом разделе MX-C1F октальным деревьям со строгой многоуровневой локализацией объектов, где в качестве критерия разбиения