Processing mutual nearest neighbor queries for moving object trajectories

Yunjun Gao, Gencai Chen, Qing Li, Baihua Zheng, Chun Li

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

6 Citations (Scopus)

Abstract

Given a set of trajectories D, a query object (point or trajectory) q, and a query interval T, a mutual (i.e., symmetric) nearest neighbor (MNN) query over trajectories finds from D within T, the set of trajectories that are among the k1 nearest neighbors (NNs) of q, and meanwhile, have q as one of their k2 NNs. This type of queries considers proximity of q to the trajectories and the proximity of the trajectories to q, which is useful in many applications (e.g., decision making, data mining, pattern recognition, etc.). In this paper, we first formalize MNN query and identify some problem characteristics, and then develop two algorithms to process MNN queries efficiently. In particular, we thoroughly investigate two classes of queries, viz. MNNP and MNNT queries, which are defined w.r.t. stationary query points and moving query trajectories, respectively. Our techniques utilize the advantages of batch processing and reusing technology to reduce the I/O (i.e., number of node/page accesses) and CPU costs significantly. Extensive experiments demonstrate the efficiency and scalability of our proposed algorithms using both real and synthetic datasets.

Original languageEnglish
Title of host publicationProceedings - 9th International Conference on Mobile Data Management, MDM 2008
Pages116-123
Number of pages8
DOIs
Publication statusPublished - 15 Sep 2008
Externally publishedYes
Event9th International Conference on Mobile Data Management, MDM 2008 - Beijing, China
Duration: 27 Apr 200830 Apr 2008

Publication series

NameProceedings - IEEE International Conference on Mobile Data Management
ISSN (Print)1551-6245

Conference

Conference9th International Conference on Mobile Data Management, MDM 2008
Country/TerritoryChina
CityBeijing
Period27/04/0830/04/08

ASJC Scopus subject areas

  • Engineering(all)

Cite this