A hierarchical model for label constraint reachability computation

作者：Chen, Luo^*; Wu, Ye; Zhong, Zhinong; Xiong, Wei; Jing, Ning

来源：Neurocomputing, 2015, 162: 67-84.

DOI：10.1016/j.neucom.2015.04.003

• Label-constraint reachability
• Bipartite hierarchical model
• Two-hop encoding
• Hierarchical labeling

Reachability query is a fundamental problem on networks currently emerging in various application domains. However, very little existing work has studied reachability with label constraints imposed on the edges/vertices of graphs. In this paper, we study the problem of answering Label-Constraint Reachability (LCR) in a labeled directed graph, i.e., whether a directed path confined to a given label set from a source query vertex to a target query vertex in the input graph exists. We propose a model called the Bipartite Hierarchical (BiHi) to speed up the LCR computation. The BiHi model adopts a representation organized as hierarchies of bipartitions, and a vertex-cover-based algorithm to label the to-most remaining subgraph. In addition, by extending the two-hop labeling, the BiHi model introduces a top-down hierarchical labeling strategy to compress the index. Extensive theoretical analyses and experimental investigations on both real-life and synthetic datasets demonstrate that our method can reduce the memory cost and construction time of index construction while maintaining high query processing efficiency.

• 出版日期2015-8-25
• 单位中国人民解放军国防科学技术大学