A Study Of Algorithms On K Hop Reachability Querying For Large Graphs

Accessibility query has been applied in many places in the directed acyclic graph’s network,such as social networks,XML document structure,biological network Analysis,metabolic network,reference network,sensor networks,database terminology relationships and other fields.Reachability query is used to answer whether node u can reach node v given any two points u and v.k-step reachability query refers to answering whether node u can reach node v within k steps for any two point.For the existing k-step reachability query algorithm,the index which is too large is built on the large graph,the index which is created can not be generally applied to any k value,and the query efficiency is common etc.this paper proposes a new k-step reachability query algorithm.And the main contributions ofthis paper are as follows:(1)The shortest path forest on the original directed acyclic graph is built and an adaptive multiplicative index of k values on the shortest path tree is bulit,on this basis a k-step reachability query algorithm based on Multi Index is designed,and the correctness and time complexity of the query algorithm are analyzed,successfully extended the k-step reachability problem to large graphs.(2)Dynamic Index for high density nodes is bulit,improved query performance for high-density query point pairs with high attention,and extended a Dynamic Index table based on double-keyword expansion on the basis of classic splay tree,and proposed a search and update algorithm for dynamic index.(3)Finally,multiplied index and dynamic index are compared with existing algorithms on 19 real datasets,the efficiency of the multiplied index in index construction time,index size,and query time is verified,efficiency of dynamic indexing in dealing with high-density point-to-point queries.