动态有向图上面向最短路径查询的新型概要技术研究

发布时间：2017-09-09 20:18

  本文关键词：动态有向图上面向最短路径查询的新型概要技术研究

  更多相关文章： 动态有向图 最短路径 概要技术 近似查询 增量计算

【摘要】：近年来,随着有向图最短路径查询应用在路网、计算机网络和社交网络等数据中的应用不断增加,有向图的最短路径查询技术受到更加广泛的关注。现有技术可以高效的处理无向图环境下的最短路径查询,然而由于有向图上最短路径查询操作的特殊性使得在有向图上的最短路径查询操作遇到了很大的挑战,有向图最短路径查询并无很好的解决方案。本文研究面向有向图准确的和带有精度保证的最短路径查询信息概要技术,并提出动态图环境下相应概要增量维护算法。首先,针对现有有向图最短路径查询技术在计算过程中在精度和速度上的缺陷,本文在代表点策略的基础上提出基于生成树编码概要结构,通过代表点策略降低内存负载极大加快概要构建速度和查询速度；同时针对通过概要结构覆盖全部查询概要结构构建过程中频繁I/O的缺陷,改进其磁盘索引结构提出轻量级的概要结构；在证明准确概要查询结果有效性的前提下,本文提出了相应的I/O高效构建算法和查询算法,并通过实验对准确概要结构性能进行验证。其次,对于用户要求在短时间内获取带有误差保证最短距离的应用请求,本文提出基于拓扑层的离散landmark快速概要结构,通过landmark节点的拓扑层次和相关信息,可以降低搜索数据大小并提前终结不必要的查询,进而加快查询速度；针对查询时在离散landmark节点集合搜索代价较大的缺陷,本文依照二分索引思想组织landmark节点构建近似概要,并针对此概要结构提出近似概要构建算法和有精度保障的查询算法；最终在真实数据集和模拟数据集上进行大量的实验,验证近似概要结构和相应查询算法的有效性。最后,本文对概要结构的高效查询和动态图环境下概要增量维护操作进行研究,为了降低整体查询代价以及动态图环境下概要增量维护代价,本文设计离散磁盘结构存储Triad信息；同时在离散磁盘结构的基础上提出增量维护缓存结构降低平均增量维护代价,并通过摊还分析证明缓存结构的有效性；最后提出基于离散磁盘结构信息获取算法和增量维护算法,并通过实验证明其有效性。本文从实际应用中对有向图最短路径查询的典型特征和调整进行分析,针对有向图最短路径概要相关技术进行研究,提出如代表点策略概要、有精度保障的近似概要以及概要结构增量维护等关键技术处理不同应用场景下的有向图最短路径查询应用。本文的概要结构以更少的内存和更短的预处理时间处理更大规模的图数据,并且以更快的速度返回最短路径查询结果。
【关键词】：动态有向图 最短路径 概要技术 近似查询 增量计算
【学位授予单位】：东北大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP333.35
【目录】：

• 摘要5-6
• ABSTRACT6-11
• 第1章 引言11-15
• 1.1 图最短路径基本概念及应用11-12
• 1.2 研究背景12-13
• 1.2.1 最短路径索引技术12
• 1.2.2 最短路径概要技术12-13
• 1.3 问题提出13
• 1.4 本文贡献13-14
• 1.5 本文工作和组织结构14-15
• 第2章 相关工作概述15-21
• 2.1 Naive最短路径查询策略15-16
• 2.2 最短路径索引技术16-18
• 2.2.1 有向图最短路径索引技术16-17
• 2.2.2 无向图最短路径索引技术17-18
• 2.3 图概要与图压缩技术18-19
• 2.3.1 最短路径概要技术18-19
• 2.3.2 图压缩技术19
• 2.4 结论19-21
• 第3章 基于代表点策略无损概要21-45
• 3.1 引言21
• 3.2 C-RTI无损概要模型21-27
• 3.2.1 基于路径距离主干节点策略概要模型22-23
• 3.2.2 生成树编码23-26
• 3.2.3 RTI概要性质26-27
• 3.3 Q-RTI无损概要27-30
• 3.3.1 不完备Triad编码27-29
• 3.3.2 基于覆盖范围均等采样策略29-30
• 3.4 无损概要构建与查询算法30-36
• 3.4.1 C-RTI概要构建算法30-32
• 3.4.2 Q-RTI概要构建策略32-34
• 3.4.3 Naive概要查询算法34-35
• 3.4.4 概要构建代价分析35-36
• 3.5 实验36-44
• 3.5.1 相关技术分析37-38
• 3.5.2 真实数据集概要性能38-40
• 3.5.3 模拟数据集概要性能40-44
• 3.6 结论44-45
• 第4章 基于拓扑层次近似概要45-67
• 4.1 引言45-49
• 4.1.1 传统最短路径快速概要技术45-46
• 4.1.2 基于无向图近似概要技术缺陷46-49
• 4.2 Naive-TL快速概要模型49-52
• 4.2.1 离散landmark49-50
• 4.2.2 Naive-TL概要结构50-52
• 4.3 BTL快速概要52-59
• 4.3.1 BTL快速概要概述52-53
• 4.3.2 二分拓扑层次landmark快速概要查询53-54
• 4.3.3 BTL概要概要构建与查询算法54-58
• 4.3.4 BTL概要性能58-59
• 4.4 实验59-66
• 4.4.1 真实数据集概要性能分析60-62
• 4.4.2 真实数据集BTL层数对概要性能的影响62-64
• 4.4.3 模拟数据集BTL概要性能64-66
• 4.5 结论66-67
• 第5章 概要高效动态维护与查询67-85
• 5.1 引言67-68
• 5.2 离散磁盘概要与查询操作68-73
• 5.2.1 离散磁盘编码结构68-71
• 5.2.2 C-RTI/Q-RTI概要查询71-72
• 5.2.3 BTL概要查询72-73
• 5.3 动态图概要结构概述73-76
• 5.3.1 动态图操作分类73-74
• 5.3.2 概要结构增量维护分析74-76
• 5.4 基于离散磁盘结构概要维护76-80
• 5.4.1 C-RTI/Q-RTI概要增量维护76-77
• 5.4.2 BTL概要更新77-78
• 5.4.3 增量维护Buffer结构78-80
• 5.5 实验80-83
• 5.5.1 真实数据集概要查询与增量计算性能81-82
• 5.5.2 BTL概要层次数对概要更新代价的影响82-83
• 5.6 结论83-85
• 第6章 结论85-87
• 6.1 本文主要贡献与结论85
• 6.2 进一步的工作85-87
• 参考文献87-91
• 致谢91-93
• 攻读硕士学位期间的项目情况93

【相似文献】

中国期刊全文数据库 前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，

本文编号：822555