Efficient Algorithm Research For Reachability Queries Based On Big Graph

The reachability query is used to answer the question of whether there is a path from a given source vertex to an end vertex in a directed graph.Reachability query processing is one of the basic operations in graph data processing.It is widely used in traffic network,social network,pattern recognition and bioinformatics network,and supports complex data analysis,the efficiency of query processing determines the efficiency of graph data analysis operations and is one of the hot issues.The paper focuses on how to efficiently deal with reachability query,the specific research contents are as follows.First,an efficient reachability query processing method named OL is proposed to solve the problem of inefficient of unreachable queries in existing 2-hop index method.OL constructs 2-hop labels based on obstacle vertexs.Compared with the existing index method to construct 2-hop labels of all the vertices,the index method based on obstacle vertexs reduces the space occupied of 2-hop labels,and can quickly answer reachability in vertices of positive and negative transitive closure.On the basis of deleting obstacle vertexs,the topology labels based on mutual inverse are proposed,which are used to answer queries that obstacle vertexs labels can not handle.Secondly,in order to solve the problem that OL is inefficient when answering unreachable queries,an optimized method named OL+ is proposed to answer reachable and unreachable queries.The efficiency of OL+ in answering unreachable queries is reflected in the proposed topological labels which are mutually exclusive and complementary,so that most of queries can be answered by topological labels in constant time.For a few remaining queries that cannot be answered by topology labels,OL+ uses the 2-hop labels based on obstacle vertexs to handle.Finally,experimentals are carried out based on 33 real datasets,the results are analyzed from index construction time,index size and reachability query time.The results verify the query efficiency of the proposed method int the paper.