大规模图中最短路径查询方法研究

发布时间：2017-08-01 06:02

  本文关键词：大规模图中最短路径查询方法研究

  更多相关文章： 大规模图 最短路径查询 树分解 距离标签 关键点集合

【摘要】：图作为描述现实世界中实体及实体间关系的基本数据结构,被广泛应用于复杂网络分析、生物信息学、地理导航、物流规划等新兴领域。随着大数据时代的到来,图数据规模迅速增长,同时数据的拓扑结构也变得越来越复杂,导致大规模图数据的分析处理面临着巨大的挑战。最短路径查询是图论研究中的核心内容之一,现实世界中的很多问题都可以转化为最短路径问题求解。然而随着网络规模的增大,经典的最短路径查询方法已无法满足大规模图的查询需求,设计更为有效的方法实现大规模图上的最短路径查询以满足各种应用需求具有一定的研究意义。本文对大规模图中最短路径查询方法进行了深入研究,发现无论是近似最短路径查询还是精确最短路径查询,在涉及大规模数据场景的现实应用中,预处理技术通常都被用来作为提高查询效率的重要手段,预处理工作完成之后,查询算法通常能够以常数时间响应查询结果。因此,基于预处理的思想,本文首先提出了一种大规模图中近似最短路径查询方法,即关键点引导的近似最短路径查询方法,该方法选择K个顶点作为图中的关键点,预处理中只计算并存储与关键点相关的最短路径,可有效减少冗余数据量的存储,同时提高预处理效率。在查询过程中,根据关键点估计最短路径,将源点与目的点之间的最短路径转化为源点与关键点之间,关键点之间,以及关键点与目的点之间的最短路径之和,从而缩小了搜索区域的范围,有效提高最短路径的查询效率。然而关键点作为图中的“枢纽”顶点,最短路径查询通过关键点采用上确界方式估计最短路径,本文方法会存在一定的误差,但通过实验验证可以在可接受的误差范围内完成大规模图中的近似最短路径查询。为满足精确查询的需求并提高预处理效率,本文提出了基于树分解与标签覆盖(Tree Decomposition and Label Cover)的最短路径查询方法,该方法首先通过树分解将大规模图映射成树结构；其次在树分解基础上创建最小化的标签集合覆盖树结构,并优化树结构和距离标签结构,有效减少冗余数据存储并缩小遍历顶点范围,提高了预处理效率的同时降低了预处理开销；最后在查询时,利用预处理创建的索引结构,只需遍历一次树结构即可完成查询,进一步提高了查询效率。最后,本文通过和已有的最短路径查询方法进行实验对比分析,验证了本文提出的两种最短路径查询方法均具有良好的预处理效率和查询效率。
【关键词】：大规模图 最短路径查询 树分解 距离标签 关键点集合
【学位授予单位】：辽宁大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP301.6;O157.5
【目录】：

• 摘要4-6
• ABSTRACT6-13
• 第1章 绪论13-18
• 1.1 研究背景13-14
• 1.2 国内外研究现状14-15
• 1.3 研究内容15-16
• 1.4 本文组织结构16-18
• 第2章 最短路径查询方法综述18-24
• 2.1 模型与问题描述18-19
• 2.1.1 图的定义与模型18
• 2.1.2 问题描述18-19
• 2.2 方法综述19-23
• 2.2.1 基于限制区域搜索技术的最短路径查询方法19-20
• 2.2.2 基于目标引导技术的最短路径查询方法20-22
• 2.2.3 基于分层技术的最短路径查询方法22-23
• 2.3 本章小结23-24
• 第3章 关键点引导的近似最短路径查询24-37
• 3.1 相关定义及方法概述24-26
• 3.1.1 基本符号定义24-25
• 3.1.2 方法概述25-26
• 3.2 关键点集合选取26-32
• 3.2.1 接近中心点选择27-29
• 3.2.2 关键点筛选29-32
• 3.3 创建距离标签库32-33
• 3.4 最短路径查询33-35
• 3.5 本章小结35-37
• 第4章 树分解与标签覆盖的最短路径查询方法37-51
• 4.1 相关定义及方法概述37-39
• 4.1.1 基本符号定义37-38
• 4.1.2 方法概述38-39
• 4.2 TDLC方法39-46
• 4.2.1 树分解39-40
• 4.2.2 创建标签覆盖40-46
• 4.3 最短路径查询46-50
• 4.4 本章小结50-51
• 第5章 实验及分析51-60
• 5.1 实验环境51
• 5.2 实验数据集51-52
• 5.3 关键引导的近似最短路径查询的实验结果与分析52-55
• 5.3.1 性能评估指标52-53
• 5.3.2 实验结果与分析53-55
• 5.4 树分解与标签覆盖的最短路径查询方法的实验结果与分析55-59
• 5.4.1 性能评估指标55-56
• 5.4.2 实验结果与分析56-59
• 5.5 本章小结59-60
• 第6章 总结与展望60-62
• 6.1 总结60-61
• 6.2 展望61-62
• 致谢62-63
• 参考文献63-66
• 攻读学位期间发表的学术论文及参加科研情况66

【参考文献】

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

1 唐晋韬;王挺;王戟;;适合复杂网络分析的最短路径近似算法[J];软件学报;2011年10期

2 张海涛;程荫杭;;基于A*算法的全局路径搜索[J];微计算机信息;2007年17期

，

本文编号：602777