基于分布式存储的大规模图的深度优先搜索算法研究

发布时间：2020-06-02 16:50

【摘要】：深度优先搜索(DFS)是一种基本的图操作,它以深度优先的形式遍历整个图,而DFS对图G中所有节点的搜索结果是一棵生成树,称为DFS-Tree。深度优先搜索算法一直是计算机科学技术领域研究的热点问题,广泛应用于连通分量计算、拓扑排序、社区检测等。随着大数据时代的来临,数据规模不断增大,数据的拓扑结构也越来越复杂,基于内存的DFS算法无法适用于大规模图数据,无法满足日益增长的数据规模和查询传输有效率的需求。因此需要设计一个更加高效的低I/O的深度优先搜索算法,运用于分布式存储的大规模图。本文深入研究了现有的深度优先搜索的半外算法,它针对存在于磁盘上的图G进行I/O高效的深度优先搜索。研究中发现,虽然此类算法在一定程度上提高了I/O的效率,但是仍无法满足分布式大规模图存储环境的下的高效I/O处理。对于分布式图存储时,半外算法得到关于图G的生成树及消除强连通时会伴随着大量的I/O,并且当原有数据存储为广度优先搜索顺序存储时,子图间存在着很多的横向边,导致算法效率下降。针对分布式存储的图G进行深度优先搜索时,设计高效I/O的划分算法将是本文研究的主要方向和内容。本文针对大规模图分布式存储特性,提出一种适用于分布式存储的图结构的深度优先搜索算法,对以DFS方式存储和BFS方式存储两种存储方式的图结构分别给出了相应的解决策略。DS算法基于根节点建立全局关系图,将原图划分成多个子图,在各子图内再次建立局部关系图,分别求得各个子图的深度优先搜索子树,最后将处理过的子树进行归并,快速建立I/O高效的深度优先搜索树。由于各个子图区域间存在可到达关系,即横向边关系。本文采用上推方法,将各个子树间暗含的关系传递到关系图中,关系图在一定的算法条件下进行判断并返回处理方法。对于BFS方式存储的图,站点间存在大量的联系需要处理,本文在各个子区域分别求得子树后,算法将对于不同类型的横向边进行判断并给出处理和连接方法。算法能够有效减少内外部I/O通信,提高I/O效率。最后,通过和传统的分布式存储的DFS算法的实验结果进行对比分析,证明本文提出的基于分布式存储的大规模图的深度优先搜索算法具有较好的DFS效率。
【图文】：

图 2-1 图G及其生成树：为了讨论当G不能保存在内存中时，，是如何在图GDFS-Tree 的。以图 2-2 为例，我们在G [10，14]的有序生同的类型。设T 是G的有序生成树，T 中出现的G的

图G的生成树及边的类型
【学位授予单位】：辽宁大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5;TP301.6

【参考文献】

相关期刊论文 前2条

1 郭双宙;徐济惠;;基于深度优先的分步分治算法研究[J];计算机技术与发展;2014年06期

2 彭建伟;殷人昆;;基于邻接表结构的进路搜索算法研究[J];计算机工程与设计;2006年18期

本文编号：2693473