Constructivity. Технология индексирования, поиска и анализа больших пространственно-временных данных
Constructivity. Технология индексирования, поиска и анализа больших пространственно-временных данных
Назначение
Стремительный рост объемов информации, а также необходимость ее анализа и осмысления приводят к развитию новых подходов к управлению многомерными данными и, в частности, к управлению пространственно-временными данными. Как правило, популярные системы управления базами данных общего назначения предусматривают для подобных целей средства пространственного индексирования и поиска, которые успешно справляются с обработкой статической информации, однако не приспособлены для данных, подлежащих перманентным изменениям. Темпоральные системы, в свою очередь, ориентированы на работу с данными, имеющими историю изменений, однако не учитывают пространственные факторы. Проблема управления данными еще более усложняется, когда они представляют собой не просто массивы точек в многомерном пространстве, а сложные структуры, например, множества мобильных объектов с протяженными границами и заданными на них отношениями ассоциации и композиции.
Например, управление масштабными архитектурно-строительными программами часто сопряжено с визуальным анализом миллионов объектов, каждый из которых имеет собственное геометрическое представление и проявляет индивидуальное динамическое поведение.Разработанная в ИСП РАН технология предназначена для создания перспективных программных систем и сервисов, оперирующих большими массивами пространственно-временных данных или динамическими сценами. Класс подобных приложений чрезвычайно широк и охватывает такие предмет предметные области, как компьютерная графика и анимация, геоинформатика, научная визуализация, автоматизация проектирования и производства, робототехника, логистика, планирование и управление проектами.
Технология предусматривает использование оригинальных методов пространственно-временного индексирования, поиска и анализа данных с учетом особенностей их геометрического представления, сложной организации и предопределенного характера динамики. Поддержка развитого набора темпоральных, метрических, топологических и ориентационных операций обеспечивает эффективное исполнение типовых пространственно-временных запросов и решение широкого круга прикладных задач, связанных с качественным и количественным анализом сцен. В частности, эффективно разрешаются запросы реконструкции сцены на заданный момент времени, выборки объектов в заданной пространственной области, поиска ближайших соседей, определения статических и динамических столкновений, бесконфликтной маршрутизации в глобальном динамическом окружении.
Реализация
Технология реализуется виде объектно-ориентированной библиотеки на языке С++, которая представляет собой расширяемый набор классов, интерфейсов и связанных с ними методов для задания пространственно-временных данных и исполнения типовых запросов к ним. Благодаря виртуализации доступа к данным, библиотека может использоваться как при разработке новых программных приложений, так и в составе унаследованных приложений с целью оптимизации их работы и расширения пользовательских функций. Организация библиотеки предусматривает средства для управления данными и изменениями, построения и обновления индексов, вычисления и кэширования производных данных, реализации операций и исполнения прикладных запросов.
Развитая система индексирования объединяет в себе бинарные деревья событий, октарные деревья пространственной декомпозиции, деревья ограничивающих объемов, деревья объектных кластеров, деревья занятости пространства. Средства конфигурирования позволяют настроить библиотеку наиболее рациональным образом для решения прикладных задач, связанных со специальными пространственно-временными запросами.
Библиотекой поддерживаются следующие виды операций:
Темпоральные операции реализуют классическую интервальную алгебру Аллена применительно к временным штампам дискретных событий и их интервалам.
Метрические операции позволяют определить индивидуальные свойства геометрических объектов и характеристики их взаимного расположения. Для твердотельных геометрических объектов могут быть вычислены диаметр, площадь, объем, центр масс, планарные проекции, а также расстояния между объектами.
Топологические операции предназначены для классификации взаимного расположения объектов и установления фактов их совпадения, пересечения, покрытия, касания, перекрытия или коллизии. По сравнению с известными топологическими моделями DE-9IM, RCC-8, RCC-3D операции допускают конструктивную имплементацию и применимы для анализа сложных объектов.
/p>Ориентационные операции обобщают известные системы исчисления направлений Франка, Фрексы, CDC, OPRA и применимы для анализа объектов с протяженными границами. Это достигается благодаря альтернативным интерпретациям классических операций исчисления направлений.Для определения столкновений в сценах используется комбинированная вычислительная стратегия, сочетающая в себе методы точного определения столкновений между геометрическими примитивами, методы локализации столкновений с помощью пространственной декомпозиции на основе регулярных октодеревьев и kd-деревьев, методы иерархий ограничивающих объемов на основе AABB и OBB параллелепипедов, методы темпоральной когерентности. Стратегия определения столкновений демонстрирует равномерно высокие показатели эффективности для сцен с разными характеристиками сложности.
Для маршрутизации в глобальном динамическом окружении разработан и реализован оригинальный метод, основанный на извлечении пространственной, метрической и топологической информации из представления сцены и на ее согласованном использовании при планировании путей. Верификация путей осуществляется с помощью популярных локальных планировщиков на основе вероятностных маршрутных сетей (PRM) и быстро растущих случайных деревьев (RRT).
Индустриальное приложение
Технология успешно апробирована при создании программной системы Synchro, предназначенной для визуального моделирования, планирования и управления масштабными индустриальными проектами.
Функции системы обеспечивают консолидацию проектных данных и календарно-сетевого графика, визуализацию проектной деятельности, определение коллизий, контроль хода проектных работ, финансовый мониторинг, подготовку иллюстрированной документации с использованием серий изображений и видеоматериалов. В настоящее время программная система с успехом применяется более чем 300 компаниями в 36 странах, в том числе, и в Российской Федерации.
Исполнитель
Перейти к списку всех проектов 