面向位置服务的最短路径缓存算法及其优化方法

发布时间：2017-06-10 21:05

  本文关键词：面向位置服务的最短路径缓存算法及其优化方法，，由笔耕文化传播整理发布。

【摘要】：随着互联网与信息化技术的迅速发展,特别是近年来,随着移动终端技术、无线网络技术、移动通信技术的飞速发展,促使了移动互联网的产生和快速的发展。人们在日常生活中对于信息获取的及时性和有效性的需求也越来越强烈,促使了基于位置服务(Location-based Services)的产生和快速发展。路网上的最短路径查询作为一种基本的基于位置的服务,受到了越来越多的关注。作为网络服务的重要组成部分,网络缓存在减少查询响应时间,提高系统效率方面有着重要的作用。因此如何利用网络缓存来提高路网上的最短路径查询效率成为一项很有挑战性的研究工作。现有的支持最短路径查询的缓存技术分为动态缓存技术和静态缓存技术。动态缓存技术在系统的运行过程中动态的更新缓存中存储的最短路径,但是存储的路径响应查询的效率较低,空间利用率不高,需要动态的更新缓存,并行性较差。静态缓存技术通过分析查询记录的统计信息来离线的构建缓存,但是对查询依赖性较大,对查询的适应性较差。因此本文重点研究支持最短路径查询的缓存构建技术。本文首先综述了现有的支持最短路径查询的缓存相关的技术,分析了现有技术的不足之处。为了定量的描述最短路径的缓存收益,基于最短路径的最优子结构性质,本文首先定义了一种缓存收益模型来指导缓存的构建过程,以解决缓存收益定量描述的问题。基于缓存收益模型,本文提出了一种全新的用于最短路径缓存构建的SPEC算法,以构建支持最短路径查询的缓存,从而有效地提高了缓存的空间利用率和查询命中率。针对缓存离线构建的冗余计算问题,本文提出了SPEC算法的改进方法,并对SPEC算法进行了改进,以进一步提高缓存的构建效率。提出了一种基于倒排索引结构的最短路径缓存索引结构,并设计了索引构建和查询的算法,有效地支持最短路径子路径的查询问题,提高了查询的效率。最后,在真实的路网数据集上进行了大量测试研究,通过实验结果本身及对实验结果的分析,证明了本文提出的缓存收益模型能够有效地衡量缓存的收益；SPEC算法能够有效的构建最短路径缓存,提高了缓存的空间利用率和查询的命中率。
【关键词】：缓存 最短路径查询 路网 面向位置的服务 收益模型
【学位授予单位】：东北大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP333
【目录】：

• 摘要5-6
• Abstract6-10
• 第1章 绪论10-14
• 1.1 研究背景10-11
• 1.2 本文的研究内容及面临的挑战11-12
• 1.3 本文的贡献12
• 1.4 本文的组织结构12-14
• 第2章 相关工作14-26
• 2.1 网络查询的缓存方法14-17
• 2.1.1 动态缓存方法14-15
• 2.1.2 静态缓存方法15-16
• 2.1.3 混合缓存方法16-17
• 2.2 最短路径查询问题17-22
• 2.2.1 最短路径查询算法17-20
• 2.2.2 图的索引结构20-22
• 2.3 搜索引擎索引介绍22-25
• 2.4 本章小结25-26
• 第3章 背景知识及问题定义26-34
• 3.1 基本概念26-31
• 3.1.1 图和最短路径基本概念26-30
• 3.1.2 缓存相关基本概念30-31
• 3.2 基于缓存查询的系统的处理过程31-32
• 3.3 问题定义32-33
• 3.4 本章小结33-34
• 第4章 最短路径缓存收益模型34-44
• 4.1 查询日志的统计分析34-36
• 4.2 路径查询代价基准36-37
• 4.3 缓存收益模型相关定义37-40
• 4.4 缓存收益模型优化方法40-43
• 4.5 本章小结43-44
• 第5章 基于收益模型的缓存构造算法与优化44-56
• 5.1 基于收益模型的缓存构造算法44-48
• 5.1.1 算法思想44-45
• 5.1.2 算法实现与分析45-48
• 5.2 算法优化策略48-50
• 5.3 缓存存储结构及优化策略50-54
• 5.4 本章小结54-56
• 第6章 实验与分析56-64
• 6.1 实验设置56-57
• 6.2 收益模型实验与分析57-58
• 6.3 代理模式下缓存方法实验与分析58-60
• 6.4 服务模式下缓存方法实验与分析60-62
• 6.5 本章小结62-64
• 第7章 结束语64-66
• 7.1 本文总结64
• 7.2 工作展望64-66
• 参考文献66-68
• 致谢68-70
• 攻硕期间参加的项目及发表的论文70

【相似文献】

中国期刊全文数据库 前10条

1 孟祥清;长度递增法求最短路径[J];河北能源职业技术学院学报;2002年04期

2 傅清祥,王朝利,孙剑峰;长廊最短路径的最优算法[J];计算机辅助设计与图形学学报;2002年12期

3 王涛,李伟生;最短路径子图[J];北方交通大学学报;2004年02期

4 徐凤生;最短路径的求解算法[J];计算机应用;2004年05期

5 王涛,李伟生;低代价最短路径树的快速算法[J];软件学报;2004年05期

6 宣士斌;基于分流算法的最短路径求解算法[J];计算机工程与应用;2004年20期

7 徐凤生;李天志;;所有最短路径的求解算法[J];计算机工程与科学;2006年12期

8 白青海;;一种求解交通图最短路径的方案[J];内蒙古民族大学学报(自然科学版);2007年02期

9 章昭辉;;一种基于离散变权网络的动态最短路径快速算法[J];计算机科学;2010年04期

10 原慧琳;汪定伟;;最短路径的可达矩阵算法[J];信息与控制;2011年02期

中国重要会议论文全文数据库 前10条

1 温粉莲;唐常杰;乔少杰;许刚;刘威;左R

本文编号：439869