Efficient Algorithm Research For Reachability Queries Based On Hybrid Label

Reachability query is one of the basic operations of the graph and is one of the hot issues that researchers pay attention to.The reachability query is used to determine whether there is a path between two nodes.The reachability query processing is widely applied to online social networks,biological networks,and transportation networks.In the past ten years,researchers have proposed many labeling schemes to improve query efficiency,but existing algorithms can only answer reachable or unreachable queries more quickly,and cannot efficiently answer both queries at the same time.This paper studies the reachability query processing method,the specific research content is as follows.Firstly,for the existing algorithms that can not effectively answer both reachable and unreachable queries,this paper proposes an algorithm based on the complete label scheme(Complete-YesNo,CYN).The basic idea of CYN is to use the No label to quickly answer the unreachable query,and then use the No label-based extended Yes label to efficiently answer the reachable query.And it is proposed to use the extended Yes label to reduce the 2hop label for efficient answering the remaining reachability queries.A corresponding efficient algorithm was proposed to quickly construct No label,extended Yes label and 2hop label.Secondly,for the CYN algorithm,the query coverage is still low and the 2hop label is large,two optimization strategies are proposed.One is to generate a Dense label for the dense node,which is used to answer the reachable query,and removes the dense node and the redundant edge from the figure to further simplify the given data graph.The other is to generate reverse label to improve the coverage of reachable and unreachable queries,further reduce the data graph,and generate smaller 2hop label to answer queries more efficiently.Finally,the algorithm and existing algorithms are compared and analyzed on 25 real datasets.The experimental results verify that the average query performance of the proposed algorithm is better than all existing algorithms.