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

《基于分布式存储的大规模图的深度优先搜索算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：单位代码：１０１４０公开４０３１５３１８８１．ＬＩＡＯＮＩＮＧＵＮＩＶＥＲＳＩＴＹ硕士学位论文ＴＨＥＳＩＳＦＯＲＭＡＳＴＥＲＤＥＧＲＥＥ中文题目：基于分布式存储的大规模图的深度优先搜索算法研究Ｒｅｓｅａｒｃｈｏｎ－ＤｅｔｈＦｉｒｓｔＳｅａｒｃｈａｌｏｒｉｔｈｍｐｇ英文题目：ｆｏｒｌａｒｇｅｓｃａｌｅｇｒａｐｈｓｂａｓｅｄｏｎｄｉｓｔｒｉｂｕｔｅｄｓｔｏｒａｇｅ论文作者：徐瑛蔚指导教师：李晓光教授专业：计算机系统结构完成时间一：二○八年五月華申请辽宁大学硕士学位论文基于分布式存

2、储的大规模图的深度优先搜索算法研究ResearchonDepth-FirstSearchalgorithmforlargescalegraphsbasedondistributedstorage作者：徐瑛蔚指导教师：李晓光教授专业：计算机系统结构答辩日期：2018年5月二○一八年五月·中国辽宁辽宁大学学位论文原创性声明本人郑重声明：所呈交的学位论文是本人在导师的指导下独立完成的。论文中取得的研宄成果除加以标注的内容外，不包含其他个人或集体己经发表或撰写过的研宄成果，不包含本人为获得其他学位而使用过的成果。对本文的研宂做出重要贡献的个人和集体均己在文

3、中进行了标注。，并表示谢意。本人完全意识到本声明的法律结果由本人承担学位论文作者签名。曰：構七＾４年／月？学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交学位论文的原件、复印件和电子版，允许学位论文被查阅和借阋Ｃ■本人授权辽宁大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编学位论文。同时授权中国学术期刊（光盘版）电子杂志社将本学位论文收录到《中国博士学位论文全文数据库》和《中国优秀硕士学位论文全文数据

4、库》并通过网络向社会公众提供信息服务。学校须按照授权对学位论文进行管理，不得超越授权对学位论文进行任意处理。保密（），在年后解密适用本授权书。（保密：请在括号“”内划Ｖ）授权人签名；：萬指导教师签名日期：年月Ｖ日日期：年ｆ月日ｆ摘要摘要深度优先搜索（DFS）是一种基本的图操作，它以深度优先的形式遍历整个图，而DFS对图G中所有节点的搜索结果是一棵生成树，称为DFS-Tree。深度优先搜索算法一直是计算机科学技术领域研究的热点问题，广泛应用于连通分量计算、拓扑排序、社区检测等。随着大数据时代的来临，数据规模不断增大，数据的拓扑结构

5、也越来越复杂，基于内存的DFS算法无法适用于大规模图数据，无法满足日益增长的数据规模和查询传输有效率的需求。因此需要设计一个更加高效的低I/O的深度优先搜索算法，运用于分布式存储的大规模图。本文深入研究了现有的深度优先搜索的半外算法，它针对存在于磁盘上的图G进行I/O高效的深度优先搜索。研究中发现，虽然此类算法在一定程度上提高了I/O的效率，但是仍无法满足分布式大规模图存储环境的下的高效I/O处理。对于分布式图存储时，半外算法得到关于图G的生成树及消除强连通时会伴随着大量的I/O，并且当原有数据存储为广度优先搜索顺序存储时，子图间存在着很多的横向边，导致算法效率下

6、降。针对分布式存储的图G进行深度优先搜索时，设计高效I/O的划分算法将是本文研究的主要方向和内容。本文针对大规模图分布式存储特性，提出一种适用于分布式存储的图结构的深度优先搜索算法，对以DFS方式存储和BFS方式存储两种存储方式的图结构分别给出了相应的解决策略。DS算法基于根节点建立全局关系图，将原图划分成多个子图，在各子图内再次建立局部关系图，分别求得各个子图的深度优先搜索子树，最后将处理过的子树进行归并，快速建立I/O高效的深度优先搜索树。由于各个子图区域间存在可到达关系，即横向边关系。本文采用上推方法，将各个子树间暗含的关系传递到关系图中，关系图在一定的算法

7、条件下进行判断并返回处理方法。对于BFS方式存储的图，站点间存在大量的联系需要处理，本文在各个子区域分别求得子树后，算法将对于不同类型的横向边进行判断并给出处理和连接方法。算法能够有效减少内外部I/O通信，提高I/O效率。最后，通过和传统的分布式存储的DFS算法的实验结果进行对比分析，证明本文提出的基于分布式存储的大规模图的深度优先搜索算法具有较好的DFS效率。关键词：深度优先搜索，分布式存储，pushup操作，DS算法IAbstractABSTRACTDepthfirstsearch(DFS)isabasicgraphoperation,whichtravers

8、esthe