Research On K-hop Reachability Query Algorithm On Large Graph

With the development and popularization of mobile Internet technology,more and more traditional services are speeding up the pace of "cloud",forming a new situation of Internet plus traditional services.In the new situation of "Internet+",the amount of data is becoming larger and larger,the structure is becoming more and more flexible,the timeliness requirement is becoming higher and the unit value density is getting lower and lower,and mankind has gradually entered the era of big data.In the face of big data,traditional relational databases seem to be unable to deal with it.Therefore,a variety of new types of databases emerge at the historic moment,among which graph database represented by Neo4j is one of them.By virtue of the unique structure of graph data,graph database plays an important role in the processing of data such as social networks.In graph data,reachability query is the most frequently used operation,which is used to answer whether there is a reachable path between two vertices.It has been widely used in communication network,social network,road traffic network and other fields.However,in some practical problems,only the information of reachability between two vertices cannot meet the need,for example,in Chinese chess manual,people not only care about whether from the current vertex to purpose vertex to eat,more concerned about the step number from the current vertex to the aim to finish eat steps,therefore the k-hop reachability queries algorithm is presented and used to answer whether k steps between two vertices can be up to.At present,several k-hop reachability query algorithms have been proposed successively,but these algorithms still have some room for improvement in the research object setting and algorithm efficiency.For example,in terms of the setting of research objects,the research objects of these algorithms are all unweighted graphs.However,in some practical problems,we often have to deal with weighted graph data.Setting the research object as unweighted graphs is not in line with the practical application,the research object of some algorithms limit for directed acyclic graph,if exist ring,the graph of data to be processed by compressed strongly connected branch structure as directed acyclic graph.It is a clever processing in the reachability query,but it is not reasonable in the k-hop reachability query.In addition,in some practical applications,we not only care about whether the two vertices are reachable within a certain cost,but also the exact cost of reachable between the two vertices,such as in communication network,to determine the best path to the purpose of network routing algorithm not only care about whether can reach between two routers,more concerned about the path cost between them,such as distance,bandwidth,the degree of congestion.To this end,this thesis mainly does the following work:Firstly,in view of the narrow limitation of the research object,the k-hop reachability query algorithm for weighted large graphs is proposed.The research object is no longer limited to unweighted graphs or acyclic graphs,and the weighted graphs and cycled graphs can also be processed normally.Secondly,to optimize the algorithm efficiency,the k-hop reachability query algorithm on weighted large graphs designs efficient index based on bidirectional shortest path index and K-reach index and query algorithm.Firstly,the approximate minimum vertex cover set of a weighted directed graph is solved,and then the index in the approximate minimum vertex cover set and the index outside the approximate minimum vertex cover set are constructed respectively based on the obtained approximate minimum vertex coverage set.In the query,the given two vertices are divided into four cases according to whether they belong to the approximate minimum vertex coverage set.By analyzing the time complexity of the algorithm,it can be seen that the algorithm can complete most k-hop of reachability queries in constant time.Thirdly,aiming at the shortest path length query,a single source shortest path length query algorithm on weighted large graphs is proposed based on the k-hop reachability query algorithm on weighted large graphs.What is solved is no longer the k-hop reachability between two vertices,but the single source shortest path length between two vertices.Fourthly,the feasibility and efficiency of the proposed algorithm are verified by comparative experiments with existing algorithms on multiple sets of real data.