路网中可变速对象k近邻连续监控  

Continuous k-nearest neighbor monitoring over moving objects with uncertain speeds in road networks

作　　者：李艳红[1] 潘怡[2] 李国徽[3] 

机构地区：[1]中南民族大学计算机科学学院,湖北武汉430074 [2]长沙学院计算科学与技术系,湖南长沙410022 [3]华中科技大学计算机科学与技术学院,湖北武汉430074

出　　处：《中南大学学报（自然科学版）》2013年第12期4916-4922,共7页Journal of Central South University:Science and Technology

基　　金：国家自然科学基金资助项目(61309002);湖北省自然科学基金资助项目(2012FFB07401)

摘　　要：研究路网中可变速对象连续k近邻查询问题(CUkNN)。提出一种不确定路网距离计算模式以计算路网中不定速移动对象和移动查询点之间的距离。基于这种距离模式,提出一种CUkNN查询监控算法以持续地获得给定时间段内查询点的可能的k近邻。为避免不必要的计算,没有计算每个结果对象的成为查询q的kNN之一、确切的概率值,而是提出一种有效的方法来将所有结果对象按照其概率值递减的顺序进行排列,选择排在前k位的对象构成最终的kNN结果集。最后通过模拟实验验证所提出算法的性能。实验结果表明,所提出的算法在CPU运行时间和精度方面均优于参照算法。The issue of processing continuous k nearest neighbor （CkNN） queries over objects moving with uncertain speeds （CUkNN） in road networks was studied. A novel model was established to estimate the distances between objects and a query client, both of which moved at uncertain speeds in the road network. Based on this distance model, a CUkNN query monitoring method was presented to continuously find the objects that could potentially be the k-nearest neighbors （kNN） of the quer~ point during the time period being monitored. To avoid unnecessary calculation, an efficient method was proposed to arrange all the potential objects in descending order of their probabilities of being a kNN of a query, rather than calculating the exact probability values. Then the first k objects were chosen to form the final kNN result set. Finally, Experimental evaluation was performed to demonstrate the efficiency of our approach. The result shows that our proposed algorithm has better performance than its competitors in CPU time and precision.

关 键 词：CkNN查询 不确定速度 CUkNN查询 路网 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]