Indexing the Trajectories of Moving Objects in Networks

Victor Teixeira de Almeida and Ralf Hartmut Güting

LG Datenbanksysteme für neue Anwendungen, FB Informatik,
Fernuniversität Hagen, D-58084 Hagen, Germany 
{victor.almeida, rhg}@fernuni-hagen.de

Abstract: The management of moving objects has been intensively studied in recent years. A wide and increasing range of database applications has to deal with spatial objects whose position changes continuously over time, called moving objects. The main interest of these applications is to efficiently store and query the positions of these continuously moving objects. To achieve this goal, index structures are required. The main proposals of index structures for moving objects deal with unconstrained 2-dimensional movement. The constrained movement is a special and a very important case of object movement. For example, cars move in roads and trains in railroads. In this paper we propose a new index structure for moving objects on networks, the MON-Tree. We describe two network models that can be indexed by the MON-Tree. The first model is edge oriented, i.e., the network is composed by edges and nodes and each edge has an associated polyline. The second one is more suitable for transportation networks and is route oriented, i.e., the network is composed by routes and junctions. A route has also an associated polyline as attribute. We propose the index in terms of the basic algorithms for insertion and querying and test our proposal in an experimental evaluation with generated data sets using as underlying networks the roads and railroads of Germany. The MON-Tree showed good scalability when increasing the number of objects and time units in the index structure, and the query window and time interval in querying. In our tests, the MON-Tree that indexes the route oriented model showed the best results.

Keywords: spatio-temporal databases, moving objects databases, index structures