Research On K-step Reachability Query Processing On Label Constrained Graphs

Reachability query is a basic operation in graph data processing,which is widely used in real life.Given a source vertex u and a target vertex v in a directed graph,the traditional reachability query is used to answer whether there is a path so that vertex u can reach vertex v.In practical application,specific information may be marked on the edge of the graph,and the connection path between nodes can be divided into long and short.Users usually need to query the results that can meet label constraints and length constraints(LCKR query).LCKR problem is widely used in social networks,financial networks and knowledge maps,but the existing algorithms can not handle LCKR queries.This paper makes an in-depth study on LCKR query processing,and the specific research contents are as follows.Firstly,LK2 H algorithm is proposed to answer LCKR query.The basic idea of LK2 H algorithm is to build a label index on every vertices in the graph in advance to save the shortest path information between the vertices,so as to speed up the query processing.LK2 H algorithm includes two parts: index construction and query processing.During index construction,a 2-hop index containing length and label information is constructed for all vertices by bidirectional pruning BFS.When querying,the query results are obtained by comparing the label indexes of the source point and the target point.At the same time,the return result is optimized,that is,when the result is determined to be unreachable,it will clarify what causes the unreachable,and return different information according to different situations.Secondly,an optimization algorithm LK2H+ is proposed to further reduce the index construction time and index size.The basic idea of LK2H+ algorithm is to select some vertices in the graph to build an index.When querying,if the query vertex has built an index,the query is answered directly based on the index,otherwise the data graph needs to be traversed.In order to reduce the cost of traversing the data graph,LK2H+ algorithm selects the vertices in the minimum vertex coverage set to build the index.Finally,taking the index size,index construction time and query response time as indicators,the performance of the two algorithms proposed in this paper is tested based on 15 real data sets.Experimental results show that LK2 H algorithm and LK2H+ algorithm can efficiently answer the k-step reachability query problem on label constraint graph.