基于历史结果缓存的路网k近邻查询算法

2021-02-11李佳佳杨亚星宗传玉夏秀峰

沈阳航空航天大学学报 2021年6期

李佳佳，杨亚星，朱睿，宗传玉，夏秀峰

(沈阳航空航天大学计算机学院，沈阳 110136)

路网中的k近邻(kNearest Neighbor，kNN)查询是在给定被查询的兴趣点(POI)集合中，返回路网中距离查询点最近的k个POI对象。近年来，随着网络通信的发展，kNN查询成了一个重要的研究课题，引起越来越多学者的关注，在地图导航、救援服务、位置感知广告服务等方面具有广阔的应用场景，例如用户查找距离最近的酒店。

路网中每天存在大量的在线k近邻查询，现有研究中要么采用在线扩展路网的查询方式，要么采用基于索引结构的查询方式，通常关注基于单一查询效率的提升，而没有考虑大量集中查询的效率。如在学校、小区等区域比较集中的查询中，存在许多结果相似的查询，但每次都需要向服务器发起查询请求，重新进行k近邻查询，大大增加了服务器的负担。为此本文提出基于历史结果缓存的k近邻查询算法(Cache basedkNN,CBkNN)，旨在重用缓存的历史k近邻查询结果，减少服务器的查询代价。

不同于现有的研究，本文研究的基于缓存的k近邻查询有以下特点：

(1)提出了共享前缀匹配模型，通过对缓存结果的共享匹配，提高缓存命中率。

(2)提出基于结点的缓存存储结构，快速查找可利用的历史查询结果，提高查询共享匹配效率。

(3)通过在真实路网中进行大量实验，结果表明，CBkNN算法比不使用缓存的INE算法快25%，比缓存算法MkNN响应时间少15%。