TY - GEN
T1 - Processing mutual nearest neighbor queries for moving object trajectories
AU - Gao, Yunjun
AU - Chen, Gencai
AU - Li, Qing
AU - Zheng, Baihua
AU - Li, Chun
PY - 2008/9/15
Y1 - 2008/9/15
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=51349101874&partnerID=8YFLogxK
U2 - 10.1109/MDM.2008.17
DO - 10.1109/MDM.2008.17
M3 - Conference article published in proceeding or book
AN - SCOPUS:51349101874
SN - 9780769531540
T3 - Proceedings - IEEE International Conference on Mobile Data Management
SP - 116
EP - 123
BT - Proceedings - 9th International Conference on Mobile Data Management, MDM 2008
T2 - 9th International Conference on Mobile Data Management, MDM 2008
Y2 - 27 April 2008 through 30 April 2008
ER -