| With the development of information technology and the emergence of new phe-nomena such as social networks and the IOT,the relationship of people to people has been extended to people to objects and objects to objects.The data generated from it has many characteristics including correlation,unstructured,and so on,and the graph struc-ture can represent these unstructured data very well.With the popularization of mobile Internet,the number of handheld devices and IOT devices has increased greatly,and the data that can be collected has an explosive growth trend.At present,China mobile users have reached 900 million,and the number of wechat monthly active accounts has reached1.151 billion.These complex relationships between massive users constitute large scale graph.Massive user generated data can be applied to a variety of scenarios,such as dis-ease outbreak path prediction,social networks,e-commerce promotion,web search,etc.Graph data analysis can quickly and accurately obtain key information from huge graph data,which has become a research hotspot.In these applications,the importance of graph topological structure query is increas-ing.In topological structure query,topological order and subgraph query occupy the main position.The topological order of query nodes helps us to analyze the dependence of graph points.subgraph query is the basic problem of graph topological structure decomposition and query.However,the traditional graph structure analysis technology is no longer suit-able for large-scale graph information acquisition.Therefore,I/O-efficient,parallel com-puting and distributed computing are used to optimize graph structure analysis.There are many issues in graph structure analysis,In this paper,three important cases are selected as the starting point from easy to hard: topological sorting,cycle search and subgraph matching,and we achieve the following results:Firstly,we study the topological ordering problem for the topological structure of di-rected acyclic graphs.Topological ordering is the most basic part of topological structure analysis,and it is also the pre step of many other queries.Topological ordering can also help us optimize the order of subgraph matching.It is difficult for traditional memory based algorithms to deal with topological ordering problems in large-scale graphs,We use I/O- efficient technologies to speed up the topological sorting in Chapter three.We pro-pose a contraction-expansion paradigm and devise an external memory algorithm based on the paradigm for the topological sorting problem.Our new algorithm is efficient due to the introduction of the new paradigm and can be implemented easily by using the fun-damental external memory primitives.We conduct extensive experiments to demonstrate the efficiency of our proposed algorithm.Secondly,for general graphs,cycle structure is a very important sub structure,which has many applications in reality,such as financial anti fraud,risk estimation and so on.However,cycle search is a computation intensive problem,which is difficult to deal with efficiently by traditional algorithm based on single thread.We apply parallel technology to cycle search,and propose a two-stage solution to cycle search.In addition,we propose a load estimation method to improve the load balance between threads.We prove that the algorithm is work-efficient,and organize experiments to verify that the algorithm has a good speedup.Finally,cycle structure matching is only a part of pattern matching in practical ap-plications.In Chapter five,we further studied more general structure matching problems.Traditional subgraph matching is mostly based on backtracking,and distributed technol-ogy can help us solve the problem of subgraph matching by means of natural connection.At present,there are many solutions,but the performances of these solutions have not been compared scientifically.We use an unified distributed platform to organize a series of experimental analysis on labeled graph and unlabeled graph.In the experiment,we chose many types of subgraph queries and data sets,and finally get an effective selection strategy in practice.Based on the above research work,this paper makes in-depth research and discussion on many aspects of graph structure analysis,and applies the new technology to the existing problems,and achieved good results.For some works,we have proved the superiority of the algorithm in theory,while some achievements have been put into practice. |
