Graph Indexing for Efficient Evaluation of Label-constrained Reachability Queries

Given a directed edge labeled graph G, to check whether vertex v is reachable from vertex u under a label set S is to know if there is a path from u to v whose edge labels across the path are a subset of S. Such a query is referred to as a label-constrained reachability (LCR) query. In this article, we present a new approach to store a compressed transitive closure of G in the form of intervals over spanning trees (forests). The basic idea is to associate each vertex v with two sequences of some other vertices: one is used to check reachability from v to any other vertex, by using intervals, while the other is used to check reachability to v from any other vertex. We will show that such sequences are in general much shorter than the number of vertices in G. Extensive experiments have been conducted, which demonstrates that our method is much better than all the previous methods for this problem in all the important aspects, including index construction times, index sizes, and query times.

Automated summary

The article presents a new method to store the transitive closure of a graph G in the form of interval spanning trees (forests). By associating each vertex v with two sequences, it efficiently checks the reachability of vertices. Extensive experiments show that this method outperforms all previous methods in terms of index construction times, index sizes, and query times.