支持动态负载的移动对象最近邻查询算法

提出一种基于双层网格索引的移动对象KNN查询算法,解决由移动对象速度变化引起的动态负载问题。算法采用粗细双层网格将不同速度的移动对象分开索引,在粗网格中索引运动速度快的对象,在细网格中索引运动速度慢的对象,减小了网格索引的维护代价,提高了KNN查询效率。针对真实数据集实验结果表明,与传统算法相比,该算法能更有效地解决动态负载问题。

K-nearest neighbor queries over moving objects for dynamic workload

In most real applications,there is the dynamic workload that is brought by the change of moving objects.This paper proposes a monitoring KNN search algorithm using two levels of grid indices structure to support the dynamic workload efficiently. The algorithm maintains two levels of the grid indices,one for fast moving objects and the other for quasi-static objects.This method can reduce the index update times with high degree and enhance the efficiency of K-Nearest Neighbor queries.The ex- periment results on the real-life datasets show that double levels of grid indices structure for monitoring K-nearest neighbor queries over moving objects is more effective than one level grid index structure to solve dynamic workload problem.