Перспективные методы индексирования пространственно-временных данных тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат наук Золотов, Владислав Александрович

• Золотов, Владислав Александрович
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Золотов, Владислав Александрович

Оглавление

Введение

Актуальность исследования

Объем и структура работы

Глава 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, С.), а также различные варианты R-деревьев, описанные в работах [3] (Guttman. А.), [4] (Sellis, Т.; Roussopoulos, N.; Faloutsos, С.), [5] (Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, В.). Данные методы требуют значительных вычислений при построении и обновлении индексов и поэтому их применение к динамическим данным крайне ограничено.

Методы компьютерной графики, в частности, методы отсечении на основе k-D деревьев [6] (Bentley, J.L.), октальных деревьев [7] (Kedem, G.), XY-деревьев [8] (Nagy, G.; Wagle, S.), puzzle-деревьев [9] (Dengel, A.), treemap-структур [10] (Shneiderman, В.) в основном используются для растеризации двумерных и трехмерных данных, однако не обеспечивают реализацию перечисленных выше функций при работе со сложно структурированными данными.

В связи с этим актуальной представляется разработка и исследование новых методов индексирования данных, учитывающих особенности приложений моделирования динамических сцен.

Целыо работы являлась разработка и исследование новых перспективных методов индексирования многомерных данных, обеспечивающих эффективное решение задач

4

моделирования динамических сцен и обуславливающих создание масштабируемых систем компьютерной графики.

Главное внимание в работе уделяется семейству сцен, представляющему широкий практический интерес и обладающему следующими свойствами:

— сцена имеют иерархическую многоуровневую организацию, объединяющую в себе сотни тысяч и миллионы объектов с индивидуальными геометрическими и динамическими характеристиками;

— объекты сцены представлены альтернативными геометрическими моделями, такими как канонические аналитические формы, сплайны, многогранники, твердотельные сборки, кинематические конструкции;

— динамика сцен строго детерминирована и порождается предопределенной последовательностью дискретных событий, связанных со вставкой, перемещением или удалением объектов (см. рис.1).

Научная новизна состоит в получении следующих результатов:

— Проведен анализ методов индексирования многомерных данных применительно к задачам моделирования динамических сцен и обоснована перспективность подходов, базирующихся на принципах декомпозиции пространства и агрегации объектов;

— Разработано семейство эффективных методов пространственно-временного индексирования сцен с использованием динамических регулярных октальных структур;

— Проведено обобщение методов на случай иерархически организованных сцен. Обобщенные варианты методов используют адаптивную стратегию развертывания октальных структур для составных объектов, обеспечивающую альтернативные способы реализации операций моделирования;

— Сформулированы и доказаны теоретические утверждения о вычислительной сложности базовых операций моделирования с использованием предложенных методов индексирования и о требованиях к объему памяти для представления структур индексов. В частности, обоснован субквадратичный характер вычислительных затрат для определения столкновений в неплотно заполненных модельных сценах и показана ограниченность требований к памяти для представления структур индексов в обобщенных методах;

Получены практические оценки сложности базовых операций моделирования как на синтезированных, так и на реальных данных, которые подтвердили эффективность предложенных методов.

Рисунок 1. Пример динамической сцены.

Теоретическая и практическая значимость полученных результатов

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

6

границ их применимости. Ряд доказанных в работе утверждений о вычислительной сложности базовых операций моделирования с использованием предложенных методов служит обоснованием их применимости при решении актуальных прикладных задач высокой размерности. К числу таких задач относится, в частности, визуализация масштабных динамических сцен в интерактивном режиме, поиск путей и планирование движения в сложном пространственном окружении, выявление конструкторских ошибок в проектных геометрических моделях, пространственно-временная верификация календарно-сетевых графиков. Несомненную практическую ценность представляет также опыт реализации предложенных методов в составе системы nD-моделирования и планирования индустриальных проектов, используемой в ряде отечественных и зарубежных компаний. Внедрение разработок позволило существенно повысить эффективность системы и расширить ее возможности в условиях перманентно растущей сложности визуальных моделей.

Апробация результатов

Основные положения работы обсуждались на семинарах ИСП РАН, семинаре им. М.Р. Шура-Бура ИПМ им. М.В. Келдыша РАН, заседании кафедры «Алгоритмов и технологий программирования» факультета инноваций и высоких технологий Московского физико-технического института (государственного университета), а также докладывались на следующих российских, европейских и международных научных форумах:

— международная конференция "XIII International Conference on Computing in Civil and Building Engineering", Ноттингем, Великобритания, 2010;

— европейская конференция "VIII European Conference on Product and Process Modeling in the Building Industry", Корк, Ирландия, 2010;

— международная конференция "XXI International Conference on Computer Graphics and Vision", Москва, 2011;

— международная конференция "XI International Conference on Construction Applications of Virtual Reality", Веймар, Германия, 2011;

— международная конференция "XIV International Conference on Computing in Civil and Building Engineering", Москва, 2012;

— международная конференция "XII International Conference on Construction applications of Virtual Reality", Тайбей, Тайвань, 2012;

— европейская конференция "IX European Conference on Product and Process Modeling in the Building Industry" Рейкьявик, Исландия, 2012;

— европейская конференция "X European Conference on Product and Process Modeling in the Building Industry", Вена, Австрия, 2014;

— XIX Байкальская Всероссийская конференция, Улан-Удэ, Максимиха, 2014.

Публикации

По теме диссертации опубликовано 13 работ, в том числе 3 статьи [11, 12, 13] в реферируемых научных журналах из списка изданий, рекомендованных ВАК РФ.

В работах [11, 12, 13] все научные результаты принадлежат автору. Научным руководителем Семеновым В.А. осуществлялась постановка и формализация задач, а также проводилась редакторская правка. В работе [14] автором предложены альтернативные схемы пространственно-временного индексирования, а также выполнен анализ сложности выполнения запросов с их использованием. В совместных работах [15, 16, 17, 18, 19, 20, 21, 22, 23] автором рассмотрены вопросы применения методов и схем индексирования для эффективного решения прикладных задач.

Личный вклад автора

Все представленные в работе результаты получены лично автором.

Объем и структура работы

Представленная работа состоит из введения, четырех глав основного содержания, заключения и списка используемых источников, включающего 93 работы. Общий объем работы составляет 123 страницы.

Глава 1 посвящена обзору существующих методов пространственного индексирования для приложений компьютерной графики и трехмерной визуализации. В этой части диссертации рассмотрены достоинства и недостатки существующих методов управления многомерными пространственными данными, выделены конструктивные принципы индексирования масштабных пространственно-трехмерных данных, а также определены наиболее перспективные в контексте решаемой задачи методы, ориентированные на широкий класс приложений компьютерной графики. В качестве основного критерия при комплексном анализе и выборе перспективных методов индексирования рассматривалась эффективность построения и обновления индексов, а также исполнения пространственных запросов поиска объектов в заданной области и

поиска коллизий между объектами сцены на их основе.

8

Проведенный сравнительный анализ фундаментальных семейств методов индексирования и поиска многомерных данных включает в себя, в частности, структуры поиска на интервалах, сбалансированные ветвистые деревья во внешней памяти, бинарные деревья пространственной декомпозиции, префиксные деревья, нерегулярные и регулярные многоуровневые сетки, метрические деревья. Данные структуры также подробно обсуждались в работе [12]. Особое внимание было уделено характерным представителям этих семейств, таким как

— сбалансированные ветвистые деревья во внешней памяти и, прежде всего семейства В- и И.-деревьев;

— бинарные деревья пространственной декомпозиции (к-с1 деревья);

— регулярные многоуровневые сетки на основе октантных и квадрантных деревьев и вложенных тетраэдральных и гексагональных блоков;

— метрические деревья для быстрого поиска соседних элементов данных в метрических пространствах (Ш181апсе-структуры, деревья покрытий и ВК-деревья);

Также были проанализированы вспомогательные методики хэширования, расщепления и кластеризации. В результате проведенного анализа выделено и исследовано семейство методов пространственной декомпозиции на основе регулярных октальных деревьев, как наиболее перспективное в контексте применимости для различных типов сцен. В основе метода лежит рекурсивное разбиение пространства сцены на восемь равных частей плоскостями, перпендикулярными каждой из координатных осей. Каждая из таких частей называется октантом. Процесс продолжается до тех пор, пока количество элементов в каждом вновь образованном октанте не окажется ниже некоторого предустановленного порога т > 1. Протяженные объекты сцены ассоциируются с минимальным октантом, в котором они могут быть размещены полностью. С результирующим пространственным разбиением ассоциируется соответствующее дерево. Корень дерева соответствует исходному ограничивающему прямоугольному параллелепипеду сцены, содержащему в себе весь набор данных, а вершины — вложенным октантам, группирующим данные на разных иерархических уровнях пространственной декомпозиции. Пример декомпозиции и полученного октального дерева приведен на рисунке 2.

Рисунок 2. Пример пространственной декомпозиции и соответствующего ей октального дерева.

Выбор обосновывается относительно невысокой вычислительной сложностью развертывания и обновления структур индексов, что является критически важным требованием для динамических данных. В качестве возможной альтернативы рассматривалось семейство методов кластеризации объектов с использованием Я-деревьев. Однако его применение представляется проблематичным из-за высоких затрат на построение и обновление индексов, связанных с необходимостью периодической кластеризации объектов на основе ресурсоемкого пространственного анализа. Кроме того, структура индексов может претерпевать значительные изменения, а эффективность исполнения запросов существенно деградировать в зависимости от очередности событий в сцене. Для сцен с интенсивной динамикой эти обстоятельства оказываются критичными.

В главе 2 детально обсуждается метод, основанный на декомпозиции пространства при помощи регулярных октальных деревьев. Для него описаны основные алгоритмы построения и обновления, выборки по заданной области, определения пересечений, а также поиска ближайших соседей. Данные алгоритмы учитывают распределение объектов по разным уровням октального представления и основаны на последовательном обходе октантов в глубину дерева с целью пространственной локализации области поиска. Тем самым, большинство октальных ячеек исключается из анализа и достигается высокая эффективность поиска. Однако известные оценки сложности в наихудшем случае приводят к пессимистическим выводам и не определяют реальных границ применимости методов декомпозиции на основе регулярных октальных деревьев. Поэтому для оценки эффективности предложенных методов необходимо получить оценки для среднего случая, наиболее применимые на практике. С целью получения этих оценок в работе вводится понятие модельного набора данных, который послужил основой для проведения необходимого вероятностного анализа. В частности, были доказаны утверждения о распределении объектов в октальном дереве, а также о вычислительной сложности выполнения основных пространственных запросов, включающих в себя построение

регулярного октального дерева, поиск объектов в заданной области, поиск ближайших соседней для заданного объекта, поиск коллизий между объектами сцены.

Проведенное исследование улучшает известные пессимистические оценки сложности разрешения пространственных запросов с применением индексов на основе регулярных октальных деревьев. Полученные оценки сложности позволяют судить о характере зависимости эффективности этих индексов от различных параметров, включающих в себя количество объектов в модельном наборе, их протяженность, а также параметр наполненности октантов. Существенной стороной проведенного в этой части работы исследования является попытка определить границы применимости рассмотренного метода декомпозиции и выработать практические рекомендации по его использованию в широком диапазоне изменения характеристик пространственных данных.

Анализ масштабных индустриальных проектов подразумевает обработку значительных объемов информации, содержащей в себе как точные трехмерные геометрические модели, так и множество событий происходящих в моделируемой сцене на протяжении заданного временного интервала. Эффективность анализа напрямую зависит от организации эффективного доступа к релевантным пространственно-временным данным, поэтому особую важность приобретает решение проблемы эффективной организации согласованных пространственно-временных индексов [13].

В главе 3 настоящей работы исследуется вопрос построения таких индексов. Для динамических сцен формализуется понятие события, а также исследуются несколько альтернативных схем пространственно-временного индексирования для приложений визуального моделирования масштабных индустриальных проектов с детерминированным характером динамики, порожденной предопределенной последовательностью событий. Они реализуют принцип декомпозиции и обеспечивают эффективный доступ к проектным данным, релевантным заданному интервалу времени и заданной области пространства. Следует отметить, что ранее предпринимались попытки использования декомпозиции для индексирования временных и пространственных данных. В частности, в ряде работ решалась задача эффективной растеризации трехмерных данных при генерации видео с использованием дерева Финкельштейна [24], временного дерева пространственной декомпозиции [25] и дерева Шена [26]. В наших работах близкие структуры с успехом применялись для определения столкновений в динамических сценах [14, 11]. Безусловно, подобные структуры представляют несомненный интерес и в контексте обсуждаемых задач визуального моделирования [27, 28, 29].

Предложенные схемы включают в себя схемы временно-пространственной и пространственно-временной декомпозиции, а также схему событийного индексирования. Схема временно-пространственной декомпозиции представляет собой естественное обобщение октального дерева на случай динамических сцен. Временное дерево выступает в роли первичного индекса, развернутого для всех событий в сцене. Пространственное дерево строится для любого заданного момента и затем обновляется на основании информации об изменениях, произошедших в заданном временном интервале.

Схему событийного индексирования можно рассматривать как развитие предыдущей схемы, поскольку в ней применяются схожие структуры и реализуются близкие принципы. Принципиальным отличием является то, что октанты октального дерева хранят в себе списки событий, происходящих в них. Для быстрого разрешения ряда пространственных запросов необходимо также поддерживать в октантах динамические списки локализуемых в них объектов. В подобном варианте схема обладает большей гибкостью, поскольку допускает несогласованные обновления этих списков.

И наконец, схема пространственно-временной декомпозиции, отличается тем, что структура пространственной декомпозиции выбирается в качестве первичного индекса. В каждом из октантов хранится временное дерево событий, происходящих в нем на протяжении всего интервала моделирования. Как и в предыдущем случае для более эффективного разрешения пространственных запросов необходимо поддерживать в октантах динамические списки локализуемых в них объектов. Такая схема также допускает несогласованные обновления этих списков.

Предложенные схемы индексирования анализируются в контексте сложности развертывания и обновления структур индексов, а также эффективности выполнения типовых запросов, возникающих в приложениях визуального моделирования проектов, включающих в себя:

— реконструкцию сцены на заданный момент времени;

— выборку объектов, лежащих в области видимости;

— анимацию выполнения проекта с изменением положения камеры;

В результате такого анализа было проведено сравнение и выработаны рекомендации по выбору той или иной схемы пространственно-временного индексирования в контексте требований, предъявляемых к конечному приложению.

Одной из принципиальных особенностей, возникающих при работе с пространственно-трехмерными данными, является их иерархическая организация, вызванная необходимостью представления сборок, состоящих из множества более мелких

12

деталей. Каждый объект сцены может иметь как свое собственное геометрическое представление, так и состоять из множества других объектов. Объекты, обладающие собственным геометрическим представлением, находятся в листовых узлах иерархии.

К сожалению, непосредственное применение методов пространственного индексирования к листовым объектам, содержащим геометрические данные, является неоптимальным подходом и приводит к неэффективному разрешению пространственных запросов. Это утверждение особенно справедливо для сцен с интенсивной динамикой. Причиной является потеря данных об иерархии объектов. Действительно, удаление или добавление составного объекта приводит к необходимости удаления или добавления всех листовых объектов, содержащихся в нем. Поскольку перемещение объекта моделируется его удалением и добавлением в новом положении, операция может оказываться крайне трудоемкой. Информация об иерархической организации объектов также может быть полезной при разрешении запросов, относящихся к конкретным объектам, а не ко всей сцене. Например, зачастую требуется найти пересечение между выделенными объектами или понять, какие части данного объекта лежат в заданной области поиска. При использовании пространственного индекса, содержащего данные только о листовых объектах сцены, семантический контекст запроса приходится обрабатывать отдельно, уже после его разрешения.

В связи с перечисленными выше недостатками в качестве метода пространственного индексирования иерархически организованных сцен в главе 4 настоящей работы была предложен комбинированный метод, предполагающий сочетание дерева представления сцены и дополнительных пространственных индексов на основе регулярных октальных деревьев. Предложенный метод может применяться к динамическим сценам, а также обеспечивает эффективную обработку запросов, обладающих дополнительным семантическим контекстом.

Для исследования этого метода определение модельного набора данных было обобщено на случай иерархически организованных данных. Проведенный теоретический анализ показал, что трудоемкость развертывания комбинированного пространственного индекса для такого набора сравнима с трудоемкостью построения регулярного октального дерева. Вместе с тем, дополнительные накладные расходы памяти на содержание комбинированного индекса также невелики по сравнению с регулярным октальным деревом.

Проведенное сравнение традиционных методов индексирования структурированных пространственно-трехмерных данных, а именно подхода связанного с использованием октального дерева для всех листовых объектов сцены и подхода

13

связанного с использованием структуры иерархии объектов в качестве пространственного индекса и предложенного подхода позволяют судить об эффективности последнего в контексте сцен с интенсивным характером динамики. Вычислительные эксперименты также подтверждают перспективность предложенного подхода. Эти обстоятельства позволяют надеяться на высокую эффективность применения предложенного метода на практике.

В пятой главе описываются вычислительные эксперименты, подтверждающие выводы, сделанные в теоретической части работы, а также перспективность предложенных методов индексирования.

В разделе 5.1 приводится описание вычислительных экспериментов с регулярными октальными деревьями. Обсуждается вопрос эффективности применения пространственных индексов на основе регулярных октальных деревьев на практике. Для этого проведено сравнение эффективности поиска коллизий между объектами (как наиболее трудоёмкого запроса) для сцен с развернутым пространственным индексом и без него. Оно показало высокую эффективность предложенных методов пространственного индексирования для разрешения пространственных запросов.

Также в данной части работы приведены результаты экспериментов по разрешению описанных в главе 2 пространственных запросов на основе регулярного октального дерева. Они показали, что предложенные модели качественно отражают характер зависимости вычислительной сложности от основных параметров сцены. Для тестирования использовались как сгенерированные модельные наборы данных с соответствующими параметрами, так и реальные трехмерные модели, применявшиеся в индустриальных проектах. В случае сгенерированных данных тесты выполнялись для множества наборов с последующим усреднением результата.

В Разделе 5.2 обсуждаются эксперименты, адресованные иерархически организованным трехмерным данным. Для тестирования использовались сгенерированные наборы данных и трехмерные модели, использовавшиеся в индустриальных проектах. Проведенные эксперименты подтвердили перспективность описанных методов для разрешения различных пространственных запросов. В частности, показано, что они обеспечивают равномерно высокую производительность для всех рассмотренных типов пространственных запросов.

На основании результатов проведенных экспериментов в работе делаются выводы об эффективности предложенных методов индексирования, а также описывается опыт их внедрения в индустриальной системе пО-моделирования и планирования.

В заключении подводятся итоги проведенного исследования.

14

Основные положения работы, выносимые на защиту

— Проведен сравнительный анализ методов индексирования многомерных данных, в результате которого выделены методы пространственной декомпозиции на основе регулярных октальных деревьев и обоснована их применимость к задачам моделирования сцен;

— Предложены и исследованы перспективные схемы пространственно-временного индексирования динамических сцен. Сформулированы и доказаны конструктивные утверждения о вычислительной сложности базовых операций моделирования и о требованиях к объему памяти для представления структур индексов;

— Предложенные схемы индексирования реализованы в виде приложения на языке программирования С++. Данная реализация послужила основой для проведения вычислительных экспериментов. На основе проведенных вычислительных экспериментов с синтезированными и реальными сценами подтверждена высокая эффективность предложенных методов индексирования;

— Проведена апробация предложенных методов индексирования в составе системы пБ-моделирования и планирования индустриальных проектов. Применение методов позволило существенно (в некоторых случаях на несколько порядков) повысить эффективность системы и расширить ее возможности в условиях перманентно растущей сложности визуальных моделей.

Глава 1. Обзор существующих методов пространственного индексирования

1.1 Классификация методов пространственного индексирования

Список литературы диссертационного исследования кандидат наук Золотов, Владислав Александрович, 2014 год

Список литературы

1. Kamel, I., Faloutsos, С. Hilbert R-tree: an improved R-tree using fractals// Proceedings of 20th International Conference on Very Large Data Bases, 3, 3, 1994.

2. Kamel, I., Faloutsos, C. On packing R-trees // Proceedings of 2nd International Conference on Information and Knowledge Management, 1993. — c. 490-499.

3. Guttman, A. R-trees: a dynamic index structure for spatial searching // Proceedings of the ACM SIGMOD Conference. — Boston, USA, 1984. — c. 47-57.

4. Sellis, T., Roussopoulos, N., Faloutsos, C. The R+-tree: a dynamic index for multi-dimentional objects // Proceedings of the 13th International Conference on Very Large Databases (VLDB). — Brighton, UK, 1987. — c. 71-79.

5. Beckmann, N., Kriegel, H. P., Schneider, R., Seeger, B. The R*-tree: an efficient and robust access method for points and rectangles // Proceedings of the ACM SIGMOD Conference.—Atlantic City, USA, 1990. —c. 322-331.

6. Bentley, J.L. Multidimensional binary search trees used for associative searching// Communications of the ACM, 9, 18, September 1975. — c. 509-517.

7. Kedem, G. The quad-CIF tree: a data structure for hierarchical on-line algorithms // Proceedings of the 19th Design Automation Conference, 1992. — c. 352-357.

8. Nagy, G., Wagle, S. Hierarchical representation of optically scanned documents // Proceedings of 7th International Conference on Pattern Recognition, 1984. — c. 347-349.

9. Dengel, A. Object-oriented representation of image space by puzzle-trees// SPIE Visual Communications and Image Processing, 1991. — c. 20-30.

10. Shneiderman, B. Tree visualization with tree maps: 2-d space-filling approach// ACM Transactions on Graphics, 1,11, 1992. — c. 92-99.

11. Золотов, В.А., Семенов, B.A Исследование и развитие метода декомпозиции для анализа больших пространственных данных.// Труды Института Системного Программирования., 25, 2013. — с. 121-166.

12. Золотов, В.А., Семенов, В.А. Современные методы поиска и индексации многомерных данных в приложениях моделирования больших динамических сцен// Труды Института системного программирования, 24, 2013. — с. 381-416.

13. Золотов, В.А., Семенов, В.А. Перспективные схемы пространственно-временной индексации для визуального моделирования масштабных

индустриальных проектов.// Труды института системного программирования, 26, 2014. —с. 175-196.

14. Semenov, V.A., Kazakov, К.А., Zolotov, V.A., Jones, H., Jones, S. Computing in Civil and Building Engineering // Combined strategy for efficient collision detection in 4D planning applications. — Nottingham, UK, June 2010. — c. 31 -39.

15. Semenov, V.A., Kazakov, K.A., Zolotov, V.A., Dengenis, T. Virtual Construction: 4D Planning and Validation.// Proceedings of the XI International Conference on Construction Applications of Virtual Reality, 2011. — c. 135-142.

16. Semenov, V.A., Kazakov, K.A., Zolotov, V.A. Advanced Spatio-Temporal Validation of Construction Schedules.// In Computing in Civil and Building Engineering, Proceedings of the 14th International Conference, 2012. — c. 184-186.

17. Semenov, V.A., Zolotov, V.A., K.A., Kazakov Spatio-temporal validation of construction projects against path conflicts.// Proceedings of 12th Conference on Construction Applications of Virtual Reality, 2012. — c. 542-551.

18. Semenov, V.A., Kazakov, K.A., Zolotov, V.A. Global Path Planning in Complex Environments using Metric and Topological Schemes.// Proceedings of the International CIB W078-W102 Conferences on Information Technology for Construction and Information and Knowledge Management in Building, 2011. — c. 87-95.

19. Semenov, V.A., Kazakov, K.A., Zolotov, V.A. Topological Mapping Complex 3D Environments Using Occupancy Octrees.// Proceedings of the XXI International Conference on Computer Graphics and Vision, 2011. — c. 111-114.

20. Semenov, V.A., Kazakov, K.A., Zolotov, V.A. Global path planning in 4D environments using topological mapping.// eWork and eBusiness in Architecture, Engineering and Construction, 2012. — c. 263-269.

21. Semenov, V.A., Kazakov, K.A., Morozov, S.V., Tarlapan, O.A., Zolotov, V.A., Dengenis, T. 4D modeling of large industrial projects using spatio-temporal decomposition // eWork and eBusiness in Architecture, Engineering and Construction. — London, UK, 2010. — c. 89-95.

22. K.C., Петрищев, В.А., Золотов, В.А., Семенов Поиск ближайших соседей в сложных трехмерных сценах// Труды XIX Байкальской Всероссийской конференции "Информационные и Математические Технологии в Науке и Управлении", 2, 2014. — с. 56-62.

23. Золотов, В.А., Петрищев, К.С. Локальное планирование движения на основе

24,

25

26

27,

28.

29,

30,

31.

32,

33.

34.

35.

36.

37.

случайных деревьев.// Труды 54 научной конференции МФТИ., 2, 2011. — с. 133135.

Finkelstein, A., Jacobs, С.Е., Salesin, D.H Proceedings of ACM SIGGRAPH // Multiresolution video, 1996. — c. 281 -290.

Zhiyan, D. Y. J., Chiang, H. W. S. Visualizatin Symposium, Pacific Vis '09 // Out-of-core volume rendering for time-varying fields using a space-partitioning (SPT) tree., 2009. — c. 73-80.

Shen, H.W., Chiang, L.J., K.L., Ma In Proceedings of IEEE Visualization // A fast volume rendering algorithm for time-varying field using a time-space partitioning (TSP) tree., 1999. —c. 371-377.

Shagam, J., Pfeiffer, J., "Dynamic Irregular Octrees," NMSU-CS-2003-004, Technical Report 2003.

Sudarsky, O., Gotsman, C. Dynamic Scene Occlusion Culling// IEEE Transactions on Visualization and Computer Graphics, 5, 1, 1999. — c. 13-29.

Whang, J.W., J.W., Song, J.Y., Chang, J.Y., Kim, W.S., Cho, C.M., Park, I.Y., Song Octree-R: An adaptive octree for efficient ray tracing.// IEEE Transactions on Visualization and Computer Graphics, 1, 4, 1995. — c. 343-349.

Bayer, R., McCreight, E. M. Organization and maintanence of large ordered indexes//Acta Informatica, 3, 1, 1972. — c. 173-189.

Abel, D. J. A B+-tree structure for large quadtrees// Computer Vision, Graphics, and Image Processing, 1, 27, July 1984. — c. 19-31.

Comer, D. The ubiquitos B-trее// ACM Computing Surveys, 2, 11, June 1979. — c. 121-137.

Space-Filling curves / Sagan, H. —-New YorkSpringer-Verlag, 1994.

Yu, Cui, Ooi, Beng Chin, Tan, Kian-Lee, Jagadish, H. V. Indexing the distance: an efficient method to KNN processing // Proceedings of the 27st international Conference on Very Large Databases (VLDB). — Roma, Italy, 2001. — c. 421-430.

Beygelzimer, A., Kakade, S., Langford, J. Cover Trees for Nearest Neighbor // Proceedings of the International Conference on Machine Learning (ICML), 2006.

Burkhard, W. A., Keller, R. Some approaches to best-match file searching// Communications of the ACM, 4, 16, April 1973. — c. 230-236.

Ciaccia, P., Patella, M., Zezula, P. Proceedings of the 23rd VLDB Conference //

M-tree An Efficient Access Method for Similarity Search in Metric Spaces, 1997. — c. 426^35.

38. Bentley, J. L. Decomposable searching problems// Information Processing Letters, 5, 8, June 1979, —c. 244-251.

39. Bentley, J. L., Wood, D. An optimal worst-case algorithm for reporting intersections of rectangles// IEEE Transactions on Computers, 7, 29, July 1980. — c. 571577.

40. Edelsbrunner, H. A new approach to rectangle intersections: part II// International Journal of Computer Mathematics, 3-4, 13, 1983. — c. 221-229.

41. McCreight, E. M. Priority search trees// SIAM Journal on Computing, 2, 14, May 1985, —c. 257-276.

42. Fuchs, H., Abram, G.D., Grant, E.D. Near real-time shaded display of rigid objects// Computer Graphics, 3, 17, 1983. — c. 65-72.

43. Fuchs, H., Kedem, Z.M., Naylor, B.F. On visible surface generation by a priori tree structures//Computer Graphics, 3, 14, 1980. — c. 124-133.

44. Henrich, A., Six, H. W., Widmayer, P. The LSD-tree: spatial access to multidimentional point an non-point data // Proceedings of the 15th International Conference on Very Large Databases (VLDB). — Amsterdam, Netherlands, 1989. — c. 45-53.

45. Lomet, D., Salzberg, B. The hB-tree: a multi-attribute indexing method with good guaranteed performance// ACM Transactions on Database Systems, 4, 15, December 1990. — c. 625-658.

46. Xu, J., Zheng, B., Lee, W. C., Lee, D. L. The D-tree: an index structure for planar point queries in location-based wireless services// IEEE Transactions on Knowledge and Data Engineering, 12, 16, December 2004. — c. 1526-1542.

47. Friedman, J. H., Bentley, J. L., Finkel, R. A. An algorithm for finding best matches in logarithmic expected time// ACM Transactions on Mathematical Software, 3, 3, September 1977. — c. 209-226.

48. Chakrabarti, K., Mehrotra, S. The hybrid tree: an index structure for high dimentional feature spaces // Proceedings of the 15th IEEE International Conference on Data Engineering. — Sydney, Australia, 1999. — c. 440-447.

49. Mount, D. M., Arya, S. ANN: a library for aproximate nearest neighbour searching // Proceedings of the 2nd Annual Center for Geometric Computing Workshop on

Computational Geometry. — Durham, 1997.

50. White, D. A., Jain, R. Similarity indexing with the SS-tree // Proceedings of the 12th IEEE International Conference on Data Engineering. —New Orleans, USA, 1996. — c. 516-523.

51. Arya, S., Mount, D. M., Netanyahu, N. S., Silverman, R., Wu, A. Y. An optimal algorithm for approximate nearest neighbour searching in fixed dimentions// Journal of the ACM, 6, 45, November 1998. — c. 891 -923.

52. O'Rourke, J. Dynamically quantized spaces for focusing Hough transform // Proceedings of the 7th International Joint Conference on Artificial Intelligence. — Vancouver, Canada, 1981. — c. 737-739.

53. Jr., K. R. Sloan Dynamicaly quantized pyramids // Proceedings of the 7th International Joint Conference on Artificial Intelligence. — Vancouver, Canada, 1981. — c. 734-736.

54. Becker, L., Hinrichs, K., Finke, U. A new algorithm for computing joins with grid files // Proceedings of the 9th IEEE Conference on Data Engineering. — Vienna, Austria, April 1993, — c. 190-197.

55. Foundations of Multidimentional and Metric Data Structures / Samet, H. — San FranciscoMorgan Kaufmann, 2006.

56. The ATree: a data structure to support a very large scientific databases / Bogdanovich, P., Samet, H.. — : Springer-Verlag Lecture Notes in Computer Science, 1990. —c. 235-248.

57. Knowlton, K. Progressive transmission of gray-scale and binary pictures by simple efficient and lossless encoding schemes// Proceedings of IEEE, 7, 68, 1980. — c. 885-896.

58. Cohen, Y., Landy, M.S., Pavel, M. Hierarchical coding of binary images// IEEE Transactions on Pattern Analysis and Machine Intelligence, 3, 7, 1985. — c. 284-298.

59. Leutenegger, S. T., Lopez, M. A., Edgington, J. STR: a simple and efficient algorithm for R-tree packing // Proceedings of the 13th IEEE International conference on Data Engineering, 1997.

60. Klosowski, J. T., Held, M., Mitchell, J. S. B., Sowizral, H., Zikan, K. Efficient collision detection using bounding volume hierarchies of k-DOPs// IEEE Transactions on Visualization and Computer Graphics, 1,4, Januray 1998. — c. 21-36.

61. Gunther, O., Bilmes, J. Tree-based access methods for spatial databases: implementation and performance evaluation// IEEE Transactions on Knowledge and Data

120

Engineering, 3, 3, 1991. — c. 342-356.

62. Gottschalk, S., Lin, M. C., Manocha, D. OBB Tree: a hierarchical structure for rapid interference detection // Proceedings of the SIGGRAPH'96 Conference. — New Orleans, USA, 1996, —c. 171-180.

63. Collision queries using oriented bounding boxes / Gottschalk, S. — Chapel HillThe University of North Carolina, 2000.

64. Theodoris, Y., Sellis, T. Optimization issues in R-tree construction // IGIS'94: Geographic Information Systems, International Workshop on Advanced Research in Geographic Information Systems, 1994.

65. Garcia, Y.J., Lopez, M.A., Leutenneger, S.T. A greedy algorithm for bulk loading R-trees // Proceedings of the 6th ACM International Symposium on Advances in Geographic Information Systems, 1997.

66. Becker, B., Franciosa, P.G., Gschwind, S., Ohler, T., Thiemt, G., Widmayer, P. Enclosing many boxes by an optimal pair of boxes // Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science, 1992.

67. Garcia, Y.J., Lopez, M.A., Leutenneger, S.T. An optimal node splitting for R-trees // Proceedings of the 24th International Conference on Very Large Data Bases, 1998.

68. Ang, C.H., Tan, T.C. New linear node splitting algorithm for R-trees // Advances in Spatial Databases - 5th International Symposium, SSD'97, 1997.

69. Hoel, E. G., Samet, H. Benchmarking spatial join operations with spatial output // Proceedings of the 21th International Conference on Very Large Databases (VLDB). — Zurich, Switzerland, 1995. — c. 606-618.

70. Cai, M., Revesz, P. Parametric rectangles: an index structure for moving objects // Proceedings of the 10th COMAD International conference on management of data, 2000.

71. Saltenis, S., Jensen, C. S., Leuteenegger, S. T., Lopez, M. A. Indexing the positions of continuously moving objects // Proceedings of the ACM SIGMOD Conference, 2000.

72. Tao, Y., Papadias, D., Sun, J. The TRP*-tree: an optimized spatio-temporal access for predictive queries // Proceedings of the 29th international conference on Very Large Data Bases (VLDB), 2003.

73. Bell, S. B. M., Diaz, B. M., Ilolroyd, F., Jackson, M. J. Spatially referenced method of processing raster and vector data// Image and Vision Computing, 4, 1, 1983. — c. 211-220.

74

75,

76

77

78,

79,

80,

81,

82,

83.

84.

85.

86.

87.

88.

Gibson, L., Lucas, D. Vectorization of raster images using hierarchical methods// Computer Graphics and Image Processing, 1, 20, 1982. —■ c. 82-29.

Адельсон-Вельский, Г. M., Ландис, Е. М. Один алгоритм организации информации//Доклады Академии Наук СССР, 146, 1962. — с. 263-266.

Red-Black Trees / Cormen, Т. Н., Leiserson, С. Е., Rivest, R. L., Stein, С.. — : Introduction to Algorithms, 2001. — с. 273-301.

Amir, A., Efrat, A., Indyk, P., Samet, H. Efficient algorithms and regular data structures for dilation, location and proximity problems// Algorithmica, 2, 30, 2001. — c. 164-187.

Schrack, G. Finding neighbors of equal size in linear quadtrees and octrees in constant time// CVGIP: Image Understanding, 3, 55, 1992. — c. 221-230.

Frank, A. U., "Problems of realizing LIS: storage methods for space related data: the fieldtree," Institute for Geodesy and Photogrammetry, Technical Report 71 1983.

The Fieldtree: a data structure for geographic information systems / Frank, A. U., R.Barrera. — : Springer-Verlag Lecture Notes in Computer Science, 1989. — c. 29-44.

Loose octrees / Ulrich, Т.. — : Game programming gemsRockland, 2000. — c. 444-453.

Samet, H. Neighbor finding techniques for images represented by quadtrees// Computer Graphics and Image processing, 1,18, 1982. — c. 37-57.

Semenov, V.A., Zolotov, V.A., Kazakov, K.A. Global path planning in 4D environments using topological mapping.// Proceedings of 12th Conference on Construction Applications of Virtual Reality, 2012. — c. 542-551.

Finkel R.A., Bentley J.L. Quad trees: a data structure for retrieval on composite keys//Acta Informatica, 4, 1, 1974. — c. 1-9.

Jimenez, P., Thomas, F., Torras, C. 3D collision detection: a survey.// Computers and Graphics, 25, 2001. — c. 269-285.

BIM, GSA, "GSA Building Information Modeling Guide Series 04 - 4D Phasing," US General Services Administration, Public Building Service, Technical Report 2009.

Heesom, D., Mahdjoubi, L. Trends of 4D CAD applications for construction planning.// Construction Management and Economics, 22, 2004. — с. 171 -182.

4D CAD and Visualization in Construction: Developments and Applications / Issa, Raja R.A., Flood, Ian, O'Brien, William J. — Gainesville, USAA. A. Balkema Publishers,

2007.

90.

91.

92.

93.

Synchro: construction project management software. [Электронный ресурс], http://www.synchroltd.com

Semenov, V.A., Anichkin, A.S., Morozov, S.V., O.A. Tarlapan, V.A. Zolotov Visual Planning and Scheduling of Industrial Projects with Spatial Factors// Proceedings of 20th ISPE International Conference on Concurrent Engineering, 2013. — c. 343-352.

Semenov, V., Anichkin, A., Morozov, S., Tarlapan, O., Zolotov, V. Effective project scheduling under workspace congestion and workflow disturbance factors.// Proceedings of the 13th International Conference on Construction Applications of Virtual Reality, 2013. —c. 239-252.

Semenov, V., Anichkin, A., Morozov, S., Tarlapan, O., Zolotov, V. Effective Project Scheduling Under Workspace Congestion And Workflow Disturbance Factors// Australian Joirnal of Construction Economics and Building Conference Series, 2, 1, 2014. — c. 35-50.

Семенов, B.A., Аничкин, A.C., Морозов, C.B., Тарлапан, О.А., Золотов, В.А. Комплексный метод составления расписаний для сложных индустриальных программ с учетом пространственно-временных ограничений// Труды Института системного программирования РАН, 26, 1, 2014. — с. 457-482.