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

路网k近邻查询返回距离查询点路径距离最短的k个兴趣点,是基于位置服务的重要技术之一。以往研究或采用无索引的在线扩展方式,或利用预先计算的索引结构来加快查找效率,前者需要大量的在线计算,后者需要较长的预处理时间及较大的存储空间,并未考虑到历史结果的复用情况,而实际应用中有大量的查询点位置相近,它们的查询结果相似。为了解决上述问题,提出了基于历史结果缓存的k近邻查询算法(CB k NN),通过选择性地缓存k近邻查询结果,对缓存的历史记录进行共享前缀检测,使更多的查询能够快速得到可利用的历史缓存记录,仅通过少量计算即可得到查询结果。实验证明,CB k NN算法在兴趣点密度较低的情况下,比无缓存算法的响应时间快25%。