Research Of Cost C Reachability Query On Graph Data

With the rapid development of the information age,the application of big data is more and more widely.And the data scale grows exponentially,it is necessary to represent the data with complex structure by graph data structure model,such as social networking,protein interaction networks,transportation networks and so on.Therefore,it is a hot topic to retrieve large-size data efficiently and quickly in recent years.However,the retrieval of graph is based on reachability queries.In fact,weighted directed acyclic graph is common in many real networks.For example,the bandwidth of a link in a communications network,the reliability of the interaction between two proteins in a PPI network,and the processing power of the warehouse / storage point in a distributed network,all of these networks are weighted DAG.Through analyzing the existing reachability query algorithms in detail,the reachability query methods DFS and BFS on the weighted graph and the UniRch-Hash algorithm on the unweighted graph cannot calculate the reachability quickly.The urgent problem is to query reachability on the weighted graph.Based on the above shortcomings,in this paper,we have proposed a Cost-based query algorithm based on pruning strategy——CQPS.The algorithm,on the weighted DAG graph,establishes the earliest index construction method and the reverse earliest index construction method,dual-zone labels and use these three indexes to achieve effective pruning;Theory proves that the named CQPS algorithm can greatly improve the response speed of reachability query.Experiments on 13 datasets with different characteristics and comparison with various algorithms,such as BFS,GRAIL,BiRch,birch-btl,and unirch-hash in terms of index construction time,index size,query time,the number of access vertices and so on,experimental results show that CQPS algorithm is superior to the above algorithms.