Affordable Access

Publisher Website

Efficient mutual nearest neighbor query processing for moving object trajectories

Authors
Journal
Information Sciences
0020-0255
Publisher
Elsevier
Publication Date
Volume
180
Issue
11
Identifiers
DOI: 10.1016/j.ins.2010.02.010
Keywords
  • Query Processing
  • Nearest Neighbor Query
  • Moving Object Trajectories
  • Algorithm
Disciplines
  • Computer Science

Abstract

Abstract 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 k 1 nearest neighbors (NNs) of q within Γ, and meanwhile, have q as one of their k 2 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., MNN P and MNN T 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 k 1 and k 2) 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.

There are no comments yet on this publication. Be the first to share your thoughts.