Efficient mutual nearest neighbor query processing for moving object trajectories

Y. Gao, B. Zheng, G. Chen, Qing Li, C. Chen, G. Chen

Research output: Journal article publicationJournal articleAcademic researchpeer-review

22 Citations (Scopus)

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 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. © 2010 Elsevier Inc. All rights reserved.
Original languageEnglish
Pages (from-to)2176-2195
Number of pages20
JournalInformation Sciences
Volume180
Issue number11
DOIs
Publication statusPublished - 1 Jun 2010
Externally publishedYes

Keywords

  • Algorithm
  • Moving object trajectories
  • Nearest neighbor query
  • Query processing

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Theoretical Computer Science
  • Software
  • Computer Science Applications
  • Information Systems and Management
  • Artificial Intelligence

Cite this