关键词: 增量式监测算法, 移动对象, 连续k近邻查询, 网络扩展, 扩展树, 道路网

Abstract: 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.

Key words: Incremental Monitoring Algorithm (IMA), moving object, Continuous k Nearest Neighbor (CkNN) query, network expansion, expansion tree, road network