Improved Graph Indexing Algorithms for Label-Constrained Reachability Queries

Abstract

Nowadays graph data have become absolutely ubiquitous in various applications starting from social/road networks to bio-medical data etc. Given such graph data, a reachability query asks if there exists a path from a source vertex to a target vertex in the graph. Due to its immense implications in both theory and applied domains, this query and many of its variants have been extensively studied in the literature. One such variant investigates the reachability between two vertices in an edge-labeled graph while constraining the label set simultaneously. This problem has recently been addressed by Valstar et al. [SIGMOD'17] who proposed an approach called the landmark indexing (LI) to support faster label-constrained reachability (LCR) queries. In this work, we introduce a simple, practical and space-e?cient solution for answering LCR queries even faster. The experimental evaluation shows signi?cant time and space e?ciency bene?ts of our proposed solution over the LI approach for this problem in both real-world and synthetic graphs.