Construtivity. The technology of indexing, searching and analysis of large spatio-temporal data

Construtivity. The technology of indexing, searching and analysis of large spatio-temporal data

Purpose

The rapid growth of information volumes, as well as the need for its analysis and interpretation, leads to the development of new approaches to the management of multidimensional data and, in particular, to the management of spatiotemporal data. Usually popular general-purpose database management systems provide spatial indexing and retrieval tools for such purposes, which successfully manage processing of static information, but are not adapted for data liable to permanent changes. In turn, temporal systems are oriented to work with the data that has a history of changes, but do not take into account spatial factors. The problem of data management is even more complicated when they are not just arrays of points in a multidimensional space, but complex structures, for example, a set of mobile objects with extended boundaries and imposed composition relations.

For example, managing large-scale architectural and construction programs often involves a visual analysis of millions of objects, each of which has its own geometric representation and exhibits individual dynamic behavior.

The technology developed at ISP RAS is intended to create promising software systems and services that operate large arrays of spatio-temporal data or dynamic scenes. The class of such applications is extremely wide and covers such subject areas as computer graphics and animation, geoinformatics, scientific visualization, CAD/CAM/CAE, robotics, logistics, planning and project management.

The technology provides for the usage of original methods of spatio-temporal indexing, search and analysis of data, taking into account the peculiarities of their geometric representation, complex organization and the predetermined nature of the dynamics. Support for a developed set of temporal, metric, topological and orientational operations ensures efficient execution of typical spatiotemporal queries and solution of a wide range of applied problems related to qualitative and quantitative analysis of scenes. In particular, queries for reconstructing a scene at the given point in time, retrieving objects in the given spatial region, finding nearest neighbors, determining static and dynamic collisions, and conflict-free routing in a global dynamic environment are effectively resolved.

Implementation

For example, managing large-scale architectural and construction programs often involves a visual analysis of millions of objects, each of which has its own geometric representation and exhibits individual dynamic behavior. The technology developed at ISP RAS is intended to create promising software systems and services that operate large arrays of spatio-temporal data or dynamic scenes. The class of such applications is extremely wide and covers such subject areas as computer graphics and animation, geoinformatics, scientific visualization, CAD/CAM/CAE, robotics, logistics, planning and project management.

The technology provides for the usage of original methods of spatio-temporal indexing, search and analysis of data, taking into account the peculiarities of their geometric representation, complex organization and the predetermined nature of the dynamics. Support for a developed set of temporal, metric, topological and orientational operations ensures efficient execution of typical spatiotemporal.

The advanced indexing system combines binary event trees, spatial decomposition trees, bounding volume trees, object cluster trees, space occupation trees. The configuration tools allow you to configure the library in the most rational way for solving applications related to special spatio-temporal queries.

The library supports the following types of operations. Temporal operations implement the classical interval algebra introduced by Allen with respect to time stamps of discrete events and their intervals. Metric operations allow you to determine the individual properties of geometric objects and the characteristics of their mutual arrangement. Diameter, area, volume, center of mass, planar projections, and distances between objects can be calculated for solid geometric objects.

Topological operations are intended to classify the relative location of objects and establish the facts of their coincidence, intersection, coverage, touch, overlap or collision. In comparison with the known topological models DE-9IM, RCC-8, RCC-3D the operations allow constructive implementation and are applicable for the analysis of complex objects. Orientational operations generalize the known Frank's and Freksa's relative orientation calculi, cardinal direction calculi (CDC), oriented point relation algebra (OPRA) and are applicable for the analysis of objects with extended boundaries. This is achieved through alternative interpretations of classical directional calculi. A computational strategy is used to determine collisions in the scenes. The strategy combines methods for the precise determination of collisions between geometric primitives, collision localization methods using spatial decomposition based on regular octrees and kd-trees, the methods of hierarchies of bounding volumes based on AABB and OBB parallelepipeds, temporal coherence methods. The collision detection strategy demonstrates uniformly high performance for scenes with different complexity characteristics.

The new original method for navigation in global dynamic environment has been developed and implemented. The method is based on extracting of spatial, metric and topological information from geometric representation of 3D scenes and its concerted usage on path planning. Global routes obtained using topological maps are verified against collisions and corrected using popular local planning algorithms like rapidly exploring random trees (RRT) and probabilistic roadmaps (PRM).

Industrial application

The technology has been successfully approved in the course of development of the Synchro software system intended for visual modeling, planning and management of large-scale industrial projects.

The functions of the system provide consolidation of project data and schedule, visualization of project activities, identification of collisions, the project progress monitoring, financial monitoring, preparation of illustrated documentation using a series of images and video materials.

Currently, the software system has been successfully applied by more than 300 companies in 36 countries.

Developer/Participant

System integration and multi-disciplinary collaborative environments