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

Road network k-nearest neighbor query algorithm based on historical result cache

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

K-nearest neighbor query returns the k points of interest with the shortest path distance from the query point,which is one of the most important location-based services.Existing methods either use an index-free online expansion method,or a pre-calculated index structure,to enhance the search efficiency.The former requires plenty of online calculations,while the latter requires longer preprocessing time and larger storage space.Without considering the reuse of historical results,there were a large number of similar query points in practical applications with the similar query results.In order to solve the above problems,a cache based k-nearest neighbor query optimization algorithm(CB k NN)based on historical results was proposed.By selecting the cached k-nearest neighbor query results and performing shared prefix detection on cached historical records,more queries could quickly obtain available historical cache records,while query results could be obtained with only a few calculations.A large number of experiments have been conducted to compare the performance the proposed algorithm with the traditional cache-free algorithm.The results show that the response time of the CB k NN algorithm is 25%faster than the no-cache algorithm when the density of interest points is low.