THREE-DIMENSIONAL MOVING OBJECT DATA COMPONENT FOR SPATIOTEMPORAL DATABASE
In-Hak Joo, Min-Soo Kim, Sung-Woong Shin
ETRI (Electronics and Telecommunications Research Institute) Spatial Information Research Team
{ihjoo, minsoo, sshin}@etri.re.kr
ABSTRACT: In this paper, we design 3D moving object data model for 3D spatiotemporal database, and develop 3D moving object data component. We define temporal data types and moving 3D geometry types for representation of moving objects. The data types and operators applied to them are implemented as a component. The implemented component supports complex trajectory queries as well as basic time-series operator, geometric relation, set operations, and distance operation. We also present a visualization application for the validation of the operators for 3D moving objects. The 3D moving object data component will be used as essential basis for development of 3D spatiotemporal DBMS, by integrating it with storage structure, spatiotemporal index, and query processor. The 3D moving object database is expected to be widely used for applications such as vehicle tracking and indoor LBS.
KEY WORDS: Moving object, Spatiotemporal, 3D, Database, GIS
1. INTRODUCTION
Spatiotemporal objects are objects that move in a geographic space and have varying position over time, and also known as moving objects. Researches about moving objects have been done in 2-dimensional space.
The impressive examples are CHOROCHRONOS project [1] that defines general data model and expresses continuous spatial attribute of moving objects, and MOST model [2][3] which expresses moving trajectory as functions with regard to time so as to predict future position. Moving objects are widely used in GIS and LBS field where tracking, monitoring, and analyses about trajectory of position are important.
However, the moving objects databases till now does not support objects in a 3-dimensional(also denoted as 3D hereafter) space, while preliminary research about 3D moving object can be found in [4]. This is thought to be due to relatively low needs as well as complexity of implementation. But recently, the interests for 3D spatiotemporal data are increasing as the needs for 3D applications such as indoor LBS(Location-Based Service) are emerging.
In this paper, we design 3D moving object data model for 3D spatiotemporal database, and develop 3D moving object data component as the first step for the 3D spatiotemporal database.
2. THREE-DIMENSIONAL MOVING OBJECT DATA MODEL
In this section, we present an overview of 3D moving object and design of 3D moving object data model.
2.1 Overview of Three-Dimensional Moving Objects The 3D moving objects are geospatial objects whose positions are continuously varying over time in 3D space, for example trajectory of flying vehicle and path of users
in an indoor environment. The visual concept of 3D moving objects are illustrated in fig.1, where the moving object is represented as point. Our work aims at how we model the 3D moving objects for a 3D spatiotemporal database to efficiently support the 3D data. In the remaining parts of this paper, it is assumed that spatiotemporal objects and moving objects have same meanings.
Figure 1. Concept of three-dimensional moving objects.
By introducing 3D moving objects, various types of query will be possible in database, to mention a few:
- Who has been in the room #412 of building #12 between 2010-09-10 13:00 and 15:00 ?
- Find a people who were closest to the entrance gate at 2009-12-25 09:00.
- Show flight number of airplanes who passed the prohibited area since 2008-01-01.
2.2 Data Types
Temporal data types. represents objects corresponding time, i.e. Instant and Period. The sequence of instant and period is defined as TemporalCollection, and an abstract class of them, Temporal is also defined.
Moving object data types. we define following basic data types that represent moving objects(Fig.2).
- TObject : an element of moving object (both geometry type and non-spatial attribute such as int, bool) in an instant of time
- MObject : a moving object over time; sequence of TObject
- MBase : sequence of TObject where element is non-spatial attribute; it has subclasses MDouble, MInteger, and MBool.
Figure 2. Moving object data types.
Moving geometry data types. represents geometry whose position is varying over time. The supported data type is MPointZ, which is the primitive 3D moving geometry data type, MPolyhedra, and MGeometryCollectionZ(Fig.3). Among the moving 3D geometry types, we focus on 3D moving point because approximating the 3D moving objects as 3D points is sufficient in most cases.
Moreover, to integrate the model with previously developed 3D spatial database, we support operations polyhedratype with MPointZ.
- MGeometryZ : abstract class of spatial moving objects who has subclasses MPointZ, MPolyhedra, and MGeometryCollection. - MPointZ : sequence of 3D point data and
corresponding time, whose position is varying over time.
Figure 3. Moving geometry data types.
2.3 Operators
Having defined the data types, we define the operators on the data types defined in section 2.2.
Time-series operators. are basic operators about time. It finds first, last, next, previous element in sequence, and find subsequence of given sequence.
Moving object operators. are basic operators of moving objects. For example,
- Snapshot finds the interpolated position of given time from the moving object sequence.
- Slice returns subpart of sequence between the two given time instants.
Spatiotemporal relations. Based on simple feature model defined by OGC(Open Geospatial Consortium) [5], 8 spatial relations between geometry(Contains, Crosses, Disjoint, Equals, Intersects, Overlaps, Touches, Within) are extended and defined for moving objects. For each time in two moving objects, the relation is evaluated to form an MBool object.
Spatiotemporal operators. are analysis functions about moving objects. Among them important examples are,
- Intersection returns common part of the moving trajectory and polyhedra(assumed to be not moving) so can find entrance and exit time of the 3D trajectory inside a given 3D region.
- Distance returns the nearest distance between two given moving object for each time, resulting MDouble value. So it can be used to find nearest trajectory from a given 3D region.
Figure 4 illustrates the example spatiotemporal operators.
Figure 4. Spatiotemporal operators.
Some other functions such as Buffer, Union and Difference also can be defined, but we do not consider them because they are not so useful or meaningless for moving points.
Trajectory relations. are the most important and practical operators of moving objects. The 5 operators shown below are developed, with the other previous operators as basic building blocks. Their visual meanings are illustrated as Fig. 5.
Relation Description
Enters A moving object is outside other moving object and then inside during its lifetime Leaves A moving object is inside other moving
object and then outside during its lifetime Passes
A moving object is outside other moving object, then inside, and finally outside during its lifetime
Insides A moving object is only inside other moving object during its lifetime
Meets
A moving object is only touches the boundary of other moving object during its lifetime
Figure 5. Trajectory relations.
2.4 Well-Known Structure of 3D Moving Objects We define WKS(Well-Known Structure) for 3D moving objects. WKS is an exchange format defined for geometry data types[5], and we extend the definition for 3D moving geometry. The WKS will be used for exchange, storage, and query about 3D moving geometry.
The WKT(Well-Known Text) for MPointZ is exemplified as follows.
MPointZ (t, x y z, t, x y z,… …)
MPointZ(2010-10-01 15:00:00, 307.66 345.02 509.54, 2010-10-01 15:01:00, 312.34 340.09 489.14, 2010-10-01 15:01:30, 305.34 333.98 480.66)
The WKB(Well-Known Binary) specification for MPointZ is shown below.
PointZ { double x;
double y;
double z;
}; // building block enum wkbByteOrder {
wkbXDR = 0, // Big Endian wkbNDR = 1 // Little Endian };
enum wkbM3DGeometryType { wkbMPointZ = 11,
… //other 3D moving geometry types wkbMPolyhedraZ = 18,
wkbMGeometryCollectionZ = 19 };
WKBMPointZ { byte byteOrder;
uint32 wkbType;
uint32 numPoints;
double instants[numPoints];
PointZ points[numPoints];
};
3. IMPLEMENTATION AND RESULT We developed the designed data types and operators as a component called 3D moving object data component.
Because of implementation difficulties, our scope is
limited to 3D moving points, while operators about general moving regions are not yet implemented. The supported data type in trajectory relation is 3D MBV(Minimum Bounding Volume) instead of generally- shaped polyhedral surface. The MBV is assumed to be not varying position and shape over time. The assumption is based on the reason that in most typical situations of application of 3D moving object, the 3D object will be buildings or their subarea, or virtual 3D zone(such as prohibited flying zone).
We develop a prototype application for test, verification, and visualization of operators on 3D moving object. Figure 6 shows a screenshot of result of Slice and Snapshot operator, where the lines represents trajectory of 3D points. Figure 7 shows the result of trajectory relations, Enters, Leaves, Passes, and Insides, where the highlighted(selected) trajectories are the ones who meet the trajectory relation with regard to a given MBV.
Figure 6. Examples of slice and snapshot relations.
Figure 7. Examples of trajectory relations.
4. CONCLUSIONS
In this paper we design 3D moving object model and develop 3D moving object data component including data types and operators. Our work is motivated by the needs of 3D moving object databases that supports management and analyses of spatial objects moving in 3D space in ubiquitous environment.
The data types and operators will be used as basis of developing a 3D spatiotemporal DBMS. The 3D
spatiotemporal DBMS can be applied to various application fields where tracking and analysis of trajectory of objects in 3D space is important. Such fields include flying objects monitoring, analyses, alert system in both public and private sectors. Another application field is indoor LBS, where trajectories of moving persons or equipments in a building need to be managed and analyzed.
As the next stage, 3D moving object DBMS is being developed now with the developed component applied.
For the task, we are planning to 1) integrate the data types and operators with storage structure, spatiotemporal index, and query processor for 3D moving objects, and 2) supporting more extended operators such as trajectory relation with general polyhedral surface.
REFERENCES
[1] A Data Model and Data Structures for Moving Object Databases. Luca Forlizzi, Ralf Hartmut Güting, Enrico Nardelli, and Markus Schneider, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, pages 319-330.
[2] Foundation for Representing and Querying Moving Objects, Ralf Hartmut Güting, Michael H. Böhlen, Martin Erwig, Christian S. Jensen, Nikos A.
Lorentzos, Markus Schneider, and Michalis Vazirgiannis, ACM Transactions on Database Systems, Vol. 25, No. 1, March 2000, pages 1-42.
[3] Modeling and Querying Moving Objects, A. Prasad Sistla, Ouri Wolfson, Sam Chamberlain, and Son Dao, Proceedings of the Thirteenth International Conference on Data Engineering, 1997, pages 422- 432.
[4] Toward a 3D Moving Object Data Model- A Preliminary Consideration, Yoshifumi Masunaga and Noriko Ukai, Proceedings of the 1999 International Symposium on Database Applications in Non-Traditional Environments, 1999. Pages 1-11.
[5] OGC 06-103r3, OpenGIS® Implementation Specification for Geographic information - Simple feature access - Part 1: Common architecture, 2006.
ACKNOWLEDGEMENTS
This research was supported by a grant (07KLSGC05) from Cutting-edge Urban Development - Korean Land Spatialization Research Project funded by Ministry of Construction & Transportation of Korean government.
