论文部分内容阅读
随着计算机和网络技术的快速提高,人们越来越多地使用图数据及其模型来描述各种实体间的复杂关系。最短路径查询作为图论中最基本最经典的问题,一直都受到人们广泛的关注。而智能移动终端设备的普及使得路网中最短路径查询的需求成为热点。缓存技术是支持智能移动终端设备的一种有效解决策略,如何有效的利用缓存技术来支持路网上最短路径查询成为了一个重要的研究问题。缓存主要分为动态缓存和静态缓存,已有的在最短路径方面的缓存技术主要是静态缓存算法。这些算法依赖查询日志中查询的统计信息,根据统计信息计算得出查询的收益,然后再选收益高的路径装入缓存。静态缓存需要每隔一段时间更新一次,比如一天更新一次。然而,这些静态算法对那些在历史记录中出现很多次而且今后还会继续出现的查询比较有效,而对于突发查询这种没有规律可循的查询,表现却并不好。因此,本文的主要研究问题是如何动态更新缓存,使缓存能够更高效地支持最短路径查询。本文首先介绍最短路径缓存问题的背景,分析了现有技术的基本情况及其不足。根据突发查询的特点,基于滑动窗口模型技术,提出了一个适合突发查询的收益模型,用来定量的评估每条路径的收益。收益模型的计算依赖于窗口中查询的频率统计,以及其频率的增长率。依据收益模型,构造了缓存的初始化构建及更新方法BRC(Benefit Reload Cache),以构造出能够处理最短路径查询的缓存并对其更新,从而保证了缓存的利用率和命中率。而后针对BRC中存在的冗余计算,提出了算法的改进和优化策略,形成了新的算法BRC*。在缓存的存储结构及查询方面,基于倒排索引技术,给出了缓存索引结构的初始化构造算法,更新算法和查询算法,有效的解决了最短路径查询问题。最后,基于真实的路网数据,实现了本文提出的BRC和BRC*算法。通过进行大量的对比试验和对实验结果的分析,证明了本文提出的缓存收益模型及算法策略能够很好的处理突发查询,依据算法构建的最短路径缓存具有高效性。