ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2020, Vol. 57 ›› Issue (9): 1949-1960.doi: 10.7544/issn1000-1239.2020.20190569

Previous Articles     Next Articles

Efficient Methods for Label-Constraint Reachability Query

Du Ming1, Yang Yun1, Zhou Junfeng1, Chen Ziyang2, Yang Anping1   

  1. 1(School of Computer Science and Technology, Donghua University, Shanghai 201620);2(School of Information Management, Shanghai Lixin Institute of Accounting and Finance, Shanghai 201620)
  • Online:2020-09-01
  • Supported by: 
    This work was supported by the National Key Research and Development Program of China (2017YFB0309800) and the National Natural Science Foundation of China (61472339, 61572421, 61873337).

Abstract: The label-constraint reachability query s→\-Lt is used to answer whether there is a directed path from s to t in the given graph, such that every label on the path belongs to L. Considering that existing approaches suffer from long index construct time, large index size and long query time, we first propose to construct a bidirectional path label index based on k nodes with large degrees, such that we can efficiently construct a smaller index, while at the same time covering a large portion of reachable information. For this large nodes based index, we propose several optimization techniques to reduce the index size, which can in turn speed up the processing of reachable queries. Further, even though the index size is small for large nodes based bidirectional path label, it does not cover all the reachable queries, and cannot avoid the graph traversal operation during query processing. To this end, we further propose a bidirectional path label index which is constructed based on all the nodes and therefore covers all the reachable information. Based on the bidirectional path label index, a label-constraint reachability query s→\-Lt can be answered by comparing the labels of the two query nodes s and t, and the traversal operation on the graph can be completely avoided during query processing. Finally, we conduct rich experiment study. In terms of index size, index construction time and query response time, the experimental results on multiple real datasets show that our approaches achieve smaller index size, and can construct the index and answer label-constraint reachability queries more efficiently compared with the state-of-the-art approaches.

Key words: graph data management, directed graph, reachability query processing, label-constraint reachability, bidirectional path label index

CLC Number: