Processing Mutual Nearest Neighbor Queries for Moving Object Trajectories

Publication Type

Conference Proceeding Article

Publication Date

4-2008

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.

Discipline

Databases and Information Systems | Numerical Analysis and Scientific Computing

Publication

9th International Conference on Mobile Data Management (MDM'08)

First Page

116

Last Page

123

Identifier

10.1109/MDM.2008.17

Publisher

IEEE

Additional URL

http://dx.doi.org/10.1109/MDM.2008.17

This document is currently not available here.

Share

COinS