基于道路网的连续k近邻查询算法

Continuous k nearest neighbor query algorithm based on road network

针对增量式监测算法(IMA)的冗余搜索问题,提出一种基于IMA改进的移动对象连续k近邻(Continuous k Nearest Neighbor,CkNN)查询处理新算法。采用增量式查询处理机制;利用距离相近的查询其查询结果大部分相同这一特性,在以查询点为中心进行网络扩展之前,首先执行一个预处理过程,分析相近的其他查询的扩展树,并重用其中的有效部分,从而避免了对道路网的盲目扩展;且在节点的网络扩展中,通过应用具有相同扩展方向的其他查询的扩展结果,不仅减少了对道路网的重复扩展,还节省了计算代价。实验结果表明,所提算法同传统算法相比较,缩短了查询响应时间,提高了运行效率,并且适用于不同类型的k近邻查询。

Concerning the problem of redundant search of Incremental Monitoring Algorithm （IMA）, this paper proposed a new algorithm of improving Continuous k Nearest Neighbor （Ck NN） queries for moving objects based on IMA. The incremental query processing mechanism was adopted. Adopting the characteristic that the close queries have similar results, a pretreatment process was first performed before the network expansion which took query point as the center, by investigating the expansion tree of other queries and reuse the effective part, thus avoiding blind expansion of road network. During the network expansion of nodes, by applying the expansion results of other queries which have the same expansion direction, not only repetitive expansion was reduced, but also computational cost was saved. The experimental results show that the query response time of proposed algorithm is reduced, the efficiency is improved compared with the traditional algorithm. In addition, the improved algorithm is applicable to different types of k nearest neighbor queries.