Research On Key Techniques Of Reachability Query For Large-scale Digraphs

With the springing up and widely used of emerging applications, includingsemantic networks, social networks, bioinformatics networks, the research onincreasingly large-scale graph data has become today’s hot and difficult problem.Reachability query is a fundamental query frenquently used in graph data analysisand processing, some complex queries can be decomposed into operation setscontaining multiple reachability queries, its effectiveness is of vital importance.Facing the large-scale graph, previous indexing schemes show the defect of queryinefficiency or excessive index costs and only support vertex reachability queries.Against the above problems, this paper studied the reachability query forlarge-scale graph. First, we proposed a planar graph cover based reachability labelingindex scheme, which uses the optimal tree as the initial process to the planar graphcover. By creating the optimal tree, a priority to find the longest chain of optimal treedecomposition and some plane processing, we obtained the planar graph cover of aDAG, which maximally retained the accessibility information of the original image;then we created labels for vertexes, ensuring answering accessibility on the planargraph cover in constant time, and then compressed the reachability transitive closure.Our index is of efficiency query, in the case of further reduced the index size.Second, we designed query algorithms based on the proposed index scheme,including reachability and path query. The path query proposed a label prefix coding,and a concept of abstract path, which can be used to identify the specific pathbetween vertices, and then optimize the path to be close to the optimal path through a"sliding window" approach.Finally, by experiments with real data sets comparing with tree cover forpath-tree, the results show that our approach has the good index size, and efficientquery response time.