Research On Depth-First Search Algorithm For Large Scale Graphs Based On Distributed Storage

Depth first search(DFS)is a basic graph operation,which traverses the whole graph in the form of depth-first.The search result of DFS for all nodes in figure G is a spanning tree called DFS-Tree.Depth first search algorithm has always been a hot topic in the field of computer science and technology.It is widely used in connected component computation,topological sorting,community detection,etc.With the advent of big data era,the scale of data is increasing,and the topology of data is becoming more and more complex.The memory-based DFS algorithm can not be applied to large-scale graph data.Unable to meet the growing data scale and query transfer efficiency requirements.So we need to design a more efficient depth-first search algorithm with low I / O,which can be used in distributed storage large-scale graph.In this paper,the existing semi-outer algorithms for depth-first search are studied in depth,which performs I / O efficient depth-first search for graphs on disk.It is found that although this kind of algorithm can improve the efficiency of I / O to some extent,it still can not satisfy the efficient I / O processing under distributed large-scale graph storage environment.For distributed graph storage,the semi-external algorithm is accompanied by a large amount of I / O when the spanning tree of the graph and the cancellation strong communication are obtained,and when the original data is stored as the breadth-priority search sequence,there are a lot of lateral edges between the sub-graphs,which leads to a decrease in the efficiency of the algorithm.In depth first search for distributed stored graphs,designing efficient I /O partitioning algorithm will be the main research direction and content of this paper.In this paper,a depth first search algorithm for distributed graph storage is proposed,which is suitable for distributed storage.The corresponding solutions to the graph structure of DFS storage and BFS storage are given respectively.Based on the root node,the algorithm establishes the global relation graph,divides the original graph into several subgraphs,establishes the local relation graph in each subgraphagain,obtains the depth first search subtree of each subgraph,and merges the processed subtree.Quickly establish I / O efficient depth first search tree.Due to the reachability of each subgraph region,that is,the lateral edge relation.In this paper,the implicit relation between each subtree is transferred to the relational graph by the method of uppush,and the graph is judged under certain algorithm conditions and the processing method is returned.For the graph stored in BFS mode,there are a lot of connections between sites to deal with.After the sub-tree is obtained in each sub-region,the algorithm will judge different types of lateral edges and give the processing and connection methods.The algorithm can effectively reduce the internal and external I / O communication and improve the I / O efficiency.Finally,by comparing the experimental results with the traditional distributed storage DFS algorithm,it is proved that the depth first search algorithm based on distributed storage has better DFS efficiency.