K-hop Reachability Queries In Large Graphs

K-hop reachability query is considered a generalization of the basic reachability, have very important applications in social networks and sensor networks. With the size of graph data continues to expand, the reachability query in large graphs has attracted more and more attention. Traditional reachability query algorithms cannot effectively support up k-hop reachability queries in large graphs, and some scalable reachability query algorithm cannot handle the k-hop reachability query due to the lack of the information of the distance. The algorithm of the reachability query cannot efficiently handle the vertices which are reachable but not k-hop reachable.In order to efficiently answer the k-hop reachability query, both the reachability query and the distance information got from the breadth-first search are used to do the k-hop reachability query. We constructed both the FELINE index and BFSI index to improve the efficiency of the k-hop reachability query. The main study include: The propose of the BFSI index which can record the distance between nodes in the BFS-trees; we propose the BFSI-S index to adapt the index to the power-law graph which can improve the cover rate of the distance information, we also find the different distribution of the in-degree and the out-degree, so we propose the BFSI-B index to limit the time of index construction. In order to further improve the query performance, we use the bidirectional search to decrease the search space, bidirectional pruning, greatly improving the efficiency of pruning.In a large number of the directed graph with different characteristics, k-hop reachability query algorithm has been tested in detail. The results show that, compared to the state-of-the-art scalable k-reach methods, under the same hardware conditions, both index size and query time are better than the latest scalable k-reach methods. Our algorithm has good scalability and time efficiency, able to adapt to the requirements of the k-hop reachability queries in large graphs.