We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Algorithms for constrained k-nearest neighbor queries over moving object trajectories.
- Authors
Yunjun Gao; Baihua Zheng; Gencai Chen; Qing Li
- 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 (C kNN) queries and historical continuous C kNN (HCC kNN) 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 C kNN 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 HCC kNN query on trajectories retrieves the constrained k nearest neighbors (C kNNs) of q at any time instance of T. We propose a suite of algorithms for processing C kNN queries and HCC kNN queries respectively, with different properties and advantages. In particular, we thoroughly investigate two types of C kNN queries, i.e., C kNNP and C kNNT, which are defined with respect to stationary query points and moving query trajectories, respectively; and two types of HCC kNN queries, namely, HCC kNNP and HCC kNNT, which are continuous counterparts of C kNNP and C kNNT, 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.
- Subjects
INFORMATION storage &; retrieval systems; GEODATABASES; GEOGRAPHIC information systems; ALGORITHMS; GEOSPATIAL data; SEARCH algorithms
- Publication
GeoInformatica, 2010, Vol 14, Issue 2, p241
- ISSN
1384-6175
- Publication type
Article
- DOI
10.1007/s10707-009-0084-5