Label Constrained Reachability Queries on Time Dependent Graphs

Label-constrained reachability (LCR) has been ex-tensively studied. However, these studies have neglected two aspects: the label sequence and time-dependent properties. When processing reachability queries, not only label presence but also label sequence and time-dependent properties should be considered. Various real-world scenarios, including vehicular networks, computing networks, and biological networks, require such queries. In this paper, we present a formal definition of time-dependent label-constrained reachability (TDLCR) queries based on LCR. These queries require both label sequence and time-dependent constraints to be considered, thus introducing a higher level of complexity. To address this challenge, we propose two indexing algorithms that are optimized for the label constraint: OneL and TD2H. OneL builds a single-label index for each vertex and provides a baseline for solving the TDLCR problem. TD2H is based on classical 2-hop index with excellent query efficiency, while innovative pruning rules and vertex order strategies are proposed to reduce indexing overhead. To further balance indexing overhead and query efficiency and to optimize the time-dependent constraint, we introduce a BII algorithm. It effectively improves index construction efficiency by building only a local index instead of a global one. Finally, experiments on many real datasets demonstrate that although the BII has a slightly inferior query time to TD2H, it has a significant advantage in the index construction.