Publication Type
Journal Article
Version
acceptedVersion
Publication Date
4-2010
Abstract
An important query for spatio-temporal databases is to find nearest trajectories of moving objects. Existing work on this topic focuses on the closest trajectories in the whole data space. In this paper, we introduce and solve constrained k-nearest neighbor (CkNN) queries and historical continuous CkNN (HCCkNN) queries on R-tree-like structures storing historical information about moving object trajectories. Given a trajectory set D, a query object (point or trajectory) q, a temporal extent T, and a constrained region CR, (i) a CkNN query over trajectories retrieves from D within T, the k (≥ 1) trajectories that lie closest to q and intersect (or are enclosed by) CR; and (ii) an HCCkNN query on trajectories retrieves the constrained k nearest neighbors (CkNNs) of q at any time instance of T. We propose a suite of algorithms for processing CkNN queries and HCCkNN queries respectively, with different properties and advantages. In particular, we thoroughly investigate two types of CkNN queries, i.e., CkNNP and CkNNT, which are defined with respect to stationary query points and moving query trajectories, respectively; and two types of HCCkNN queries, namely, HCCkNNP and HCCkNNT, which are continuous counterparts of CkNNP and CkNNT, respectively. Our methods utilize an existing data-partitioning index for trajectory data (i.e., TB-tree) to achieve low I/O and CPU cost. Extensive experiments with both real and synthetic datasets demonstrate the performance of the proposed algorithms in terms of efficiency and scalability.
Keywords
Query processing, Nearest neighbor, Moving object trajectory, Algorithm
Discipline
Databases and Information Systems | Numerical Analysis and Scientific Computing
Publication
Geoinformatica
Volume
14
Issue
2
First Page
241
Last Page
276
ISSN
1384-6175
Identifier
10.1007/s10707-009-0084-5
Publisher
Springer Verlag
Citation
GAO, Yunjun; ZHENG, Baihua; CHEN, Gencai; LI, Qing; and CHEN, Chun.
Algorithms for Constrained k-Nearest Neighbor Queries over Moving Object Trajectories. (2010). Geoinformatica. 14, (2), 241-276.
Available at: https://ink.library.smu.edu.sg/sis_research/1984
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
https://doi.org/10.1007/s10707-009-0084-5
Included in
Databases and Information Systems Commons, Numerical Analysis and Scientific Computing Commons