Algorithms for Nearest Neighbor Search on Moving Object Trajectories |
| |
Authors: | Elias Frentzos Kostas Gratsias Nikos Pelekis Yannis Theodoridis |
| |
Affiliation: | (1) Information Systems Laboratory, Department of Informatics, University of Piraeus, 80 Karaoli-Dimitriou St., 18534 Piraeus, Greece;(2) Data and Knowledge Engineering Group, R. A. Computer Technology Institute, Patras, Greece |
| |
Abstract: | Nearest Neighbor (NN) search has been in the core of spatial and spatiotemporal database research during the last decade.
The literature on NN query processing algorithms so far deals with either stationary or moving query points over static datasets
or future (predicted) locations over a set of continuously moving points. With the increasing number of Mobile Location Services
(MLS), the need for effective k-NN query processing over historical trajectory data has become the vehicle for data analysis, thus improving existing or
even proposing new services. In this paper, we investigate mechanisms to perform NN search on R-tree-like structures storing
historical information about moving object trajectories. The proposed (depth-first and best-first) algorithms vary with respect
to the type of the query object (stationary or moving point) as well as the type of the query result (historical continuous
or not), thus resulting in four types of NN queries. We also propose novel metrics to support our search ordering and pruning
strategies. Using the implementation of the proposed algorithms on two members of the R-tree family for trajectory data (namely,
the TB-tree and the 3D-R-tree), we demonstrate their scalability and efficiency through an extensive experimental study using
large synthetic and real datasets.
|
| |
Keywords: | nearest neighbor moving objects NN query processing on R-tree-like structures storing historical trajectories |
本文献已被 SpringerLink 等数据库收录! |
|