公路网移动终端的KNN查询技术

KNN Query Technology of Mobile Terminals in Highway Networks

公路网中移动兴趣点(POIs)的查询处理是一个难点,目前的研究多基于欧氏距离对静态POIs进行处理,不能很好地适应移动环境下终端弱连接和频繁移动的需要.文中在公路网移动计算场景下,设计了一种存储分区数据对象的结构来表示公路网图形模型,提出适用于移动终端的连续KNN查询(CQ-KNN)算法.该算法改进了Wang等提出的MKNN算法,将逐层渐近探测和检索边列表结合起来进行近邻查询,避免了MKNN算法在限定层数不够却不得不执行范围查询时所带来的开销;同时使用缓存策略来支持移动终端提交的连续查询请求,并给出基于广播位置失效报告的缓存一致性维护策略.仿真结果表明,CQ-KNN算法较MKNN算法有更快的CPU处理速度和更短的网络响应延时,并且能支持移动终端的离线KNN近似查询.

The dynamic POIs（Points of Interest） in highway networks are difficult to query.Most current researches focus only on the static POIs with the help of the Euclidean distance metrics,which are inefficient for the weak connection and frequent movement of mobile terminals in mobile computing environments.In order to solve this problem,a structure to store cell data objects is designed to describe the highway network graph model,and a continuous KNN（K-Nearest Neighbor） query（CQ-KNN） algorithm for mobile terminals is presented.For the purpose of improving the existing MKNN algorithm proposed by Wang et al,CQ-KNN algorithm combines the progressive probe and the edge information list retrieval,thus saving the cost of range query execution in MKNN algorithm when fixed layers are insufficient.Moreover,CQ-KNN algorithm employs the local cache strategy to support the conti-nuous query of mobile terminals and adopts the cache consistency maintenance strategy based on the invalid broadcast location report.Simulated results show that CQ-KNN algorithm is superior to MKNN algorithm in terms of CPU processing speed and network response delay,and that it effectively supports the off-line approximate KNN query of mobile terminals.