DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs

Download PDF

Abstract

Many real-world graphs, e.g., social networks, biological networks, knowledge graphs, naturally come with edge-labels, with different labels representing different relationships between nodes. On such edge-labeled graphs, a fundamental query is a label-constrained reachability (LCR) query, where we are given a source 𝑠, a target 𝑡, a label set Ψ, and the goal is to determine if there exists any path from 𝑠 to 𝑡 such that for any edge on the path the label belongs to Ψ. The existing indexing scheme for LCR queries still focuses on static graphs, despite the fact that many edge-labeled graphs are dynamic in nature. Motivated by limitations of existing solutions, we present a study on how to effectively maintain the indexing scheme on dynamic graphs. Our proposed approach is based on the state-of-the-art 2-hop index for LCR queries. In this paper, we present efficient algorithms for updating the index structure in response to dynamic edge insertions/deletions and demonstrate the correctness of our update algorithms. Following that, we present that adopting a query-friendly but update-unfriendly indexing scheme results in surprisingly superb query/update efficiency and outperforms those update-friendly ones. We analyze and demonstrate that the query-friendly indexing scheme actually achieves the same time complexity as those of update-friendly ones. Finally, we present the batched update algorithms where the updates may include multiple edge insertions/deletions. Extensive experiments show the effectiveness of the proposed update algorithms, query-friendly indexing scheme, and batched update algorithms.