Download INFORMATIK

Transcript
Efficient k-Nearest Neighbor Search on
Moving Object Trajectories
Ralf Hartmut Güting, Thomas Behr, Jianqiu Xu
Database Systems for New Applications,Mathematics and Computer Science
University of Hagen, Germany
{rhg,thomas.behr,jianqiu.xu}@fernuni-hagen.de
July 25, 2009
Abstract
With the growing number of mobile applications, data analysis on large sets of historical moving objects trajectories becomes increasingly important. Nearest neighbor search is a fundamental
problem in spatial and spatio-temporal databases. In this paper we consider the following problem:
Given a set of moving object trajectories D and a query trajectory mq, find the k nearest neighbors
to mq within D for any instant of time within the life time of mq. We assume D is indexed in a
3D-R-tree and employ a filter-and-refine strategy. The filter step traverses the index and creates a
stream of so-called units (linear pieces of a trajectory) as a superset of the units required to build
the result of the query. The refinement step processes an ordered stream of units and determines the
pieces of units forming the precise result.
To support the filter step, for each node p of the index, in preprocessing a time dependent coverage
function Cp (t) is computed which is the number of trajectories represented in p present at time t.
Within the filter step, sophisticated data structures are used to keep track of the aggregated coverages
of the nodes seen so far in the index traversal to enable pruning. Moreover, the R-tree index is
built in a special way to obtain coverage functions that are effective for pruning. As a result, one
obtains a highly efficient k-NN algorithm for moving data and query points that outperforms the two
competing algorithms by a wide margin.
Implementations of the new algorithms and of the competing techniques are made available as
well. Algorithms can be used in a system context including, for example, visualization and animation
of results. Experiments of the paper can be easily checked or repeated, and new experiments be
performed.
1 Introduction
Moving objects databases have been the subject of intensive research for more than a decade. They allow
one to model in a database the movements of entities and to ask queries about such movements. For some
applications only the time-dependent location is of interest; in other cases also the time dependent extent
is relevant. Corresponding abstractions are a moving point or a moving region, respectively. Examples
of moving points are cars, air planes, ships, mobile phone users, or animals; examples of moving regions
are forest fires, the spread of epidemic diseases and so forth.
Some of the interest in this field is due to the wide-spread use of cheap devices that capture positions,
e.g. by GPS, mobile phone tracking, or RFID technology. Nowadays not only car navigation systems,
but also many mobile phones are equipped with GPS receivers, for example. Vast amounts of trajectory
data, i.e., the result of tracking moving points, are accumulated daily and stored in database systems
[13, 34, 28].
There are two kinds of such databases. The first kind, sometimes called a tracking database, represents a set of currently moving objects. One is interested in continuously maintaining the current
1