面向不确定移动对象的连续K近邻查询算法

Continuous K-Nearest Neighbor Queries for Uncertain Moving Objects

近年来,位置服务等领域急需解决的一个难点问题是不确定移动对象连续K近邻查询.基于此情况,文中提出高效的面向不确定移动对象的连续K近邻查询算法.首先提出2种预测移动对象可能区域算法Max Min与Rate,利用最近一段时间窗口内的位置采样、速度和方向预测移动对象在查询时刻到未来I区间可能的位置区域.同时使用最小距离与最大距离区间描述移动对象到查询对象的距离.然后采用优化的基于模糊可能度判定的排序方法查找查询对象的K近邻.最后在真实和合成的大规模移动对象数据集上验证文中方法的有效性.

problem in location-based services is continuous K-nearest neighbor （KNN） queries for uncertain moving objects. An efficient algorithm for continuous K-nearest neighbor queries for uncertain moving objects is proposed. Firstly, two solutions, MaxMin and Rate, are proposed to predict the possible location range of the moving object in the time interval by utilizing the sampling points with velocities in the recent time window. A closed interval of minimum and maximum distances is employed to represent the distance between the query object and the moving object. Secondly＇ an optimized ranking method based on vague possibility decision is proposed to quickly find KNNs of the query object. Finally, experimental results on real and synthetic large-scale datasets demonstrate the effectiveness of the proposed algorithm.