Efficient k-nearest neighbor search on moving object trajectories
With the growing number of mobile applications, data analys is on large sets of historical mov- ing objects trajectories becomes increasingly important. Nearest neighbor search is a fundamental problem in spatial and spatio-temporal databases. In this p aper 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 orde red 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 C p ( t ) is computed which is the number of trajectories represented in p present at time t . Within the filter step, sophisticated data structures are us ed to keep track of the aggregated coverages of the nodes seen so far in the index traversal to enable pruni ng. Moreover, the R-tree index is built in a special way to obtain coverage functions that are e ffective for pruning. As a result, one obtains a highly efficient k -NN algorithm for moving data and query points that outperfo rms the two competing algorithms by a wide margin. Implementations of the new algorithms and of the competing t echniques are made available as well. Algorithms can be used in a system context including, f or example, visualization and animation of results. Experiments of the paper can be easily checked or repeated, and new experiments be performed.
Nutzung und Vervielfältigung:
Alle Rechte vorbehalten