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

摘要：

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

关键词：公路网、移动终端、位置相关查询、K近邻、缓存、移动计算

所属期刊栏目：40

分类号：TP311(计算技术、计算机技术)

资助基金：国家"973"计划项目2007CB07100.2007CB07106

在线出版日期：2012-05-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：138-145,158