CYPK-KNN:一种改进的移动对象KNN查询算法

CYPK-KNN:A Modified Monitoring KNN Queries Over Moving Objects Algorithm

目的改进YPK-KNN算法以提高其查询效率.方法利用网格对移动对象进行索引.确定一个尽可能小的搜索区域,使得此区域一定包含距离查询点最近的K个移动对象,然后在此区域内完成查询点的KNN查询.结果针对真实数据集的实验结果表明在同等条件下,改进算法的查询执行时间明显小于原算法.而且随着移动对象个数的增加和网格划分粒度的减小这种优势随之增加.结论改进的移动对象YPK-KNN查询算法有效提高了原算法的查询效率.

YPK-KNN is a typical k-nearest neighbor queries＇ algorithm over moving objects. This paper proposes an algorithm to improve the efficiency of YPK-KNN query algorithm. Our method uses a grid to index moving objects. First, it determines a searching area as small as possible, which must include the k-nearest neighbor of the query point; second, it completes the query answer in this region. Based on the real-life datasets, the experiment results show that our advanced algorithm＇s runtime is much shorter than before under the same conditions. And the advantage is more and more obvious with the numbers of the moving objects increasing and the grid granularity decreasing. K-nearest neighbor query over moving objects is very important for LBS. This paper has improved the typical YPK-KNN queries＇ algorithm and has proved that our modified algorithm is more effective than before.