一种障碍空间中移动对象的连续k最近邻查询方法

A Continuous k-Nearest Neighbor Query Method for Moving Data in Obstructed Spaces

针对时空数据库中的连续移动对象的最近邻查询问题,提出COp KNN(continuous obstructed possible k-nearest neighbor)查询:在二维空间中,给定一个移动查询点q、一组移动查询对象集合P和一组多边形障碍物集合O,根据障碍距离的概念,查询q所有可能的k最近邻集合。由于移动对象本身的不确定性以及现实生活中障碍物的存在,已有的查询方式不再适用COp KNN查询。COp KNN查询包括三个子过程:根据可视图、R树和堆排序的概念,给出计算两点之间障碍距离(大于等于欧几里得距离)的方法;基于R树的查询方式查找在用户给定时间段内q所有可能的k最近邻结果集(初步结果,也叫候选集);采用Mindist(E,q)和候选集更新算法Updata C(pn)对k最近邻结果集进行剪枝,得到较为精确的k最近邻结果集。实验数据集和障碍物集均采用真实的数据集,理论研究和实验结果表明,该方法具有良好的效率。

To solve the nearest neighbor query of continuously moving objects in Spatio-temporal database,we study novel form of continuous k-nearest neighbor query in the presence of obstacles,namely continuous obstructed possible k-nearest neighbor（COp KNN） search. Given a data set P,an obstacle set O,and a query point q in a two-dimensional space,a COp KNN query retrieves all possible k-nearest neighbors of each point on q according to the obstructed distance. Duo to the inherent of moving data objects and the existence of obstacles in our real life,previous techniques to answer nearest neighbor（NN） query cannot be directly applied to the COp KNN problem.The P COp KNN query method mainly includes three sub-algorithms： according to the concept of Visibility graph,R-tree and Heap Sort,given the method of calculation of the obstacle distance（greater than or equal Euclidean distance） between two points; find all possible k-nearest neighbors of q between user given time period based on Rtree; Using Mindist（E,q） and the candidate set update algorithm Updata C（pn） to prune k NNs to get the correct k-nearest neighbors. Experimental data sets and obstacle sets are all based on real data sets,theoretical and experimental results show that the method with good efficiency mentioned herein.