K Nearest Neighbors Search for the Trajectory of Moving Object

摘要：

This paper addresses the problem of finding the K nearest neighbors for the trajectory of moving object in the context where the dataset is static and stored in an R-tree. By converted into discovering the K nearest neighbors of the line segment, this kind of query is simplified. Several distance functions between MBRs and line segments are defined and used to prune search space. and minimize the pruning distance. Based on branch-and-bound technique and proposed pruning, updating and visiting heuristics, recursive depth-first and heap-based best-first algorithms are presented. An extensive study based on experiments performed with synthetic dataset shows that best-first algorithm outperforms the depth-first algorithm.

关键词： nearest neighbor search branch-and-bound algorithms R-treese

作者: LIU Xiao-feng LIU Yun-sheng XIAO Yin-yuan

作者单位: College of Computer Science and Technology Huazhong University of Science and Technology Wuhan 430074, Hubei, China

会议类型: 国际会议

会议名称: 2005年无线通信、网络和移动计算国际会议

会议地点: 武汉

会议语种:英文

页码: 1304-1307

在线出版日期: 2005-09-23（万方平台首次上网日期，不代表论文的发表时间）