Efficient Processing Research For Reachability Queries Based On Big Graph

Reachability query processing based on graph is one of the hot issues in the management of map data,can be applied to many areas of real life,including semantic network,Internet,telecommunications networks,wireless sensor networks and biological information network.These data have the characteristics of large amount and high complexity,how to answer the reachability query is a challenging problem currently.In this paper,the reachability query processing method is studied from the following aspects.First of all,it is found that the existing reachability query algorithm has the problems of large index size,long indexing time,long query processing time,and can not deal with the problem of increasing the proportion of reachable queries efficiently,In this paper,to solve these problems were studied.Secondly,this paper proposes the concept of the optimal spanning tree,reduces the search space of reachable queries,and proves that it is superior to other spanning trees in the aspect of obtaining reachable information.This paper proposes an algorithm with linear time for constructing the index of both time and space,and proposes reciprocal topological order of topological sort order and its reverse order based on depth first,which can reduce the search space of unreachable queries.Thirdly,according to the fact that the reduced graph has no redundant edges and has no equivalent nodes and the information can not be changed,the reachability query algorithm based on embedded tree is proposed.On the basis of reciprocal topological labels,the algorithm extends the bidirectional reciprocal topological labels to reduce the search space of reachability queries.Then,by analyzing the nature of the vertex labels in the embedded tree,we can speed up the query processing speed according to the order of bidirectional reciprocal topology and the upper and lower root information.Finally,experiments are carried out on 20 real datasets,and the results are compared and analyzed.The results show that the proposed method is efficient and scalable.