Research On Accessibility Query Algorithm Based On DAG

The reachability query processing of directed acyclic graph(DAG)is one of the hot issues in graph data management.It can be applied to many areas of real life,including semantic web,Internet,telecommunication network,wireless sensor network,social network and bio information network.The reachability query is based on a directed acyclic graph G,given any two nodes u and v,to answer whether u can reach v.By analyzing the existing accessibility query algorithms,it is found that the existing algorithms have a long time to construct the index and the efficiency of the query is low.This paper mainly studies the accessibility query processing from the above two aspects,and the research content is as follows.First,an index building algorithm SP based on shadow location is proposed.The SP algorithm sets the label for each vertex based on the interval extension strategy.Given the need to deal with n vertices,different from the previous algorithms require multiple search operations to complete the processing of the current vertex,SP algorithm based on shadow positioning technology,it will be processed vertices are stored in the pending list and stack to be scanned,for each vertex in the stack in the list to record the scanning position the existing methods of O(logn)search cost reduced to O(1)cost,accelerate the efficiency of the index construction.Secondly,a coding scheme based on two-way interval extension and huge vertex is proposed to improve the efficiency of query processing.By extending the forward and reverse intervals to specify the corresponding index labels for each node,the ability to filter the interval is enhanced.a bit label filtering strategy with huge vertices is proposed to further enhance the processing ability.Selecting k maximal hop nodes to construct label.we set up the compressed bit labels to answer the reachable queries quickly.Finally,experiments are carried out on 25 real datasets.The method and existing methods are compared and analyzed.The experimental results verify the efficiency and scalability of the proposed method.