Research On Key Technique Of Reachability Queries Processing Within K-steps On Graph Data

With the coming of the big data and the scale of data increases exponentially,more and more complex structure data is represented as graph structure model.Nodes represent entities in real life,while edges represent the relations between entities.This model has been widely used in many fields in real life,including social networks,protein interaction network,traffic network,etc.So how to retrieve effectively has been a hot topic in recent years.Reachability query is one of the main research directions on graph data.However,compared with the classic reachability query,reachability queries within k steps can provide more information for users in many practical applications.So efficiently answering reachability queries within k steps becomes one of hot research issues in graph data management.This paper researches reachability queries within k steps on the graph data from the following several aspects.The main tasks of this paper are as follows:Firstly,considering that existing methods are difficult to avoid duplicated checking the unreachable vertex pairs.Secondly,we propose a new algorithm,namely UniRch-Hash(a unidirectional search algorithm based on hash table).This algorithm is based on unidirectional double interval labeling indexes and bidirectional pruning strategy which are both proposed in BiRch-BTL.To improve the performance of the algorithm,UniRch-Hash overcomes this challenge by recording the unreachable vertex pairs and its steps using hash table.Thirdly,UniRch-Hash is not suitable for processing the query which the vertex pairs are located in different branches.We further propose RE-UniRch-Hash algorithm based on bidirectional double interval labeling indexes.At last,20 real datasets are employed to validate the performances of our method in terms of different metrics,including indexing time,index size,query processing time,the number of visited vertexes,the size of hash table and scalability.Experimental results show that UniRch-Hash and RE-UniRch-Hash are both superior to other competitive algorithms.