Modeling Storing and Mining Moving Object Databases

Download Report

Transcript Modeling Storing and Mining Moving Object Databases

Modeling Storing and Mining
Moving Object Databases
Proceedings of the International Database Engineering
and Applications Symposium (IDEAS’04)
Sotiris Brakatsoulas
Dieter Pfoser
Nectaria Tryfona
Presentation by
Michael J. Dudley
What is a Moving Object Database?

A Moving Object Database (MOD)
consists of:

Spatial Data

Infrastructure information


Non-spatial Data


Roads, Buildings, Obstructions, etc …
Other thematic information
Trajectories

New area of research
Spacial and Non-spacial Data


Both scenarios are well explored
research topics
Many DBMS allow for their
manipulation.
Trajectories


New field of research
No commercial DBMS are available to
manage the trajectory data
Handling Trajectories

Pre-process the data


Data Modeling


Deal with errors in positional measurements
Define a conceptual model to meet systems
requirements
Data Storage

Logical data models, data types and query
processing issues
What is a MOD use for?


Registering current information is not
enough
A MOD must be able to extract further
knowledge about a system

“Mini-World Fortune Teller”
ΙΧΝΗΛΑΤΗΣ System

ΙΧΝΗΛΑΤΗΣ means “Path Finder” in Greek


I will use the English translation when discussing this system
The Path Finder System(PFS) of Athens, Greece

Focuses on extracting further information about the
movement of vehicles in the Athens municipal area.



Additional information about traffic conditions
Optimal routes
Prediction of troublesome situations
PFS History

PFS is a research project focusing on the
development of a traffic management system

Two main goals


Registration of the semantics of moving object data in an
object-oriented way resulting in a MOD
Adaptation of well known and widely used mining
functions of characterization, clustering, and association
in the moving object application domain and their
expression through SML, allowing for a formal application
in MOD
PFS Core Components
The Charateriser
 Cluster Finder
 Associator

All three are used to perform data
extraction on the MOD
Article vs. Presentation

Article





Section 2 – Organization of the database
Section 3 – Pre-processing, modeling and storage issues
related to trajectory data
Section 4 – Architecture and components of the PFS
Section 5 – Analyses the mining process and presents the
spatial mining language
Presentation


I will focus on Section 2 for the remainder of this
presentation
Please contact me if you would like a full copy of this article.
Organizing the MOD

It is essential to study




the movement of objects
their properties and relations
Fundamental concept of movements of
objects
After defining the semantics we
organize them into a database, the
MOD
The semantics of movement

Represent a moving object as point
object


Volume and size do not play a critical role
This point object can be represented in
a 3D graph


Space (x, y)
Time (t)
The semantics of movement



Need the moving object’s position on a
continual basic
Current GPS and telecommunications
technologies obtain position at discrete
instances of time
By interpolating these samples we can extract
the movement of the object

Linear interpolating takes the sample positions
and makes them the ends points of line segments.
The combination of the line segments makes an
line in three-dimensional space
The semantics of movement
The solid line below represents the movement of a point object. Space (xand y-axes) and time (t-axis) are combined to form a 3D-area.
Modeling Storing and Mining Moving Object Databases pg 3.
The semantics of movement
The figure below shows a spatiotemporal space (the cube in solid lines) and
several trajectories (the solid lines) contained in it. Time moves in the upward
direction, and the top of the cube is the time of the most recent position. The
wavy-dotted lines on top symbolize the growth of the cube with time.
Modeling Storing and Mining Moving Object Databases pg 3.
The semantics of movement

In this study, the previous trajectory
representation in three-dimensional space
was chosen to be adequate to derive the
properties and relationships of the object
movement.

Answers both simple and complex questions


Which area did a vehicle cover during its trip?
Which vehicles left Athens after midnight moving East
and were found close to each other 2 hours later?
The semantics of movement

Properties – based on requirements


The speed of the movement
The heading


The covered area



The direction of the vehicle
Indicating the area the vehicle covered during
its trip
The traveled distance
The traveled time
The semantics of movement

Relationships


Relations between a trajectory and its
spatial environment
Relations among trajectories
The semantics of movement

Relations between a trajectory and its spatial
environment (trajectory/spatial)

Infrastructure elements


Roads, Buildings, Parks, etc …
Imaginary entities


City boundaries or query regions
In a temporal context these spatial entities
become three-dimensional represented by a
3D region
The semantics of movement

Five basic spatial relationships





Stay Within
Bypass
Leave
Enter
Cross
Modeling Storing and Mining Moving Object Databases pg 3.
The semantics of movement

Relations among trajectories (trajectory/trajectory)


Additional relevant to spatial relationship
Based on topological reasoning
The semantics of movement

Five common relations among trajectories





Intersect
Meet
Equal
Near
Far
Modeling Storing and Mining Moving Object Databases pg 3.
The Database Schema of MOD


Previous concepts needs to be
organized to define the data model of
MOD
Use the class diagram of UML for the
conceptual representation due to it’s
popularity and high degree of
comprehension and expressiveness.
The Database Schema of MOD
Modeling Storing and Mining Moving Object Databases pg 4.
The Database Schema of MOD

Trajectory Class:

To capture a trajectory:




Trajectory ID
Vehicle ID
Position
Set of Operations





GetPosition
GetSpeed
GetTime
TravelledDistance
GetHeading
Modeling Storing and Mining Moving Object Databases pg 4.
The Database Schema of MOD

3D-region Class


Denotes the spatial
environment of the
trajectory
In this case it shows
total covered area
Modeling Storing and Mining Moving Object Databases pg 4.
The Database Schema of MOD

Trajectories have one or more relations
with other trajectories or their 3D-region
class.
Modeling Storing and Mining Moving Object Databases pg 4.
The Database Schema of MOD

This style of representation has the
advantage of describing two basic
concepts


The trajectory of the moving object by
keeping track of its movement
The moving object by recording its last
known position
Questions

The road network of Athens, Greece
Modeling Storing and Mining Moving Object Databases pg 5.