Efficient Mutual Nearest Neighbor Query Processing for Moving Object Trajectories
Given a set D of trajectories, a query object q, and a query time extent Γ, a mutual (i.e., symmetric) nearest neighbor (MNN) query over trajectories finds from D, the set of trajectories that are among the k1 nearest neighbors (NNs) of q within Γ, and meanwhile, have q as one of their k2 NNs. This type of queries is useful in many applications such as decision making, data mining, and pattern recognition, as it considers both the proximity of the trajectories to q and the proximity of q to the trajectories. In this paper, we first formalize MNN search and identify its characteristics, and then develop several algorithms for processing MNN queries efficiently. In particular, we investigate two classes of MNN queries, i.e., MNNP and MNNT queries, which are defined with respect to stationary query points and moving query trajectories, respectively. Our methods utilize the batch processing and reusing technology to reduce the I/O cost (i.e., number of node/page accesses) and CPU time significantly. In addition, we extend our techniques to tackle historical continuous MNN (HCMNN) search for moving object trajectories, which returns the mutual nearest neighbors of q (for a specified k1 and k2) at any time instance of Γ. Extensive experiments with real and synthetic datasets demonstrate the performance of our proposed algorithms in terms of efficiency and scalability.
Query processing, Nearest neighbor query, Moving object trajectories, Algorithm
Databases and Information Systems | Numerical Analysis and Scientific Computing
Data Management and Analytics
GAO, Yunjun; ZHENG, Baihua; CHEN, Gencai; LI, Qing; CHEN, Chun; and CHEN, Gang.
Efficient Mutual Nearest Neighbor Query Processing for Moving Object Trajectories. (2010). Information Sciences. 180, (11), 2176-2195. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/1986
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.