孙海龙 ,王霓虹 ,王春艳

(东北林业大学a.信息与计算机工程学院；b.图书馆,哈尔滨 150040)

1 概述

随着无线通信技术的发展和具有GPS 定位功能的移动电话、PDA 等便携设备的普及,基于位置的服务(Location Based Service,LBS)得以快速发展,已广泛应用于地理信息系统、应急服务、汽车导航和旅游路径规划等领域[1]。空间查询与基于位置服务密切相关,其中,道路网络环境下移动对象的连续K 最近邻查询(Continouns K Nearest Neighbors,CKNN)是一类重要的查询请求,能够在道路网络环境下不断查找距离给定的查询对象最近的K个最近邻目标,例如,在消防指挥中,查找距离指挥中心最近的4 辆消防车。解决此问题的关键在于：(1)快速实时计算任意2 个移动对象之间的最短路径；(2)移动对象位置更新后查询结果的维护与管理。

国内外针对道路网络的CKNN 查询问题,学者们进行了深入研究。文献[2]提出IMA/GMA方法,处理查询对象和兴趣点对象在道路网上任意移动的CKNN 查询问题。该方法是处理基于道路网络的CKNN 查询经典算法,采用基于内存的数据结构存储网络边、结点以及查询信息,提出IMA/GMA 算法处理查询请求。IMA 算法从查询对象所在边开始扩展网络边,并遍历网络边上的兴趣点对象,形成初始KNN 查询结果集,同时以查询点为根,建立查询扩展树,处理查询请求、移动对象和道路边权重更新时的连续查询请求。GMA 采用IMA和共享执行机制,算法使用“序列”思想,即：序列上的查询请求结果为序列上的对象和序列端点处KNN 结果的并集,当多个查询请求处在同一序列上时可共享已获得的查询结果。……