DBL: Efficient Reachability Queries on Dynamic Graphs (Complete Version)

Qiuyi Lyu, Yuchen Li, Bingsheng He, Bin Gong

Abstract

Reachability queries are fundamental to graph analysis, yet they pose significant challenges in dynamic networks where edges are frequently added. Most existing solutions rely on maintaining a Directed Acyclic Graph (DAG) by collapsing Strongly Connected Components (SCCs), which incurs a massive overhead during updates. This paper proposes DBL, a DAG-free indexing framework. DBL utilizes Dynamic Landmark (DL) labels to quickly identify reachable pairs and Bidirectional Leaf (BL) labels to prune unreachable ones. Experimental results on large-scale real-world datasets demonstrate that DBL achieves orders of magnitude faster index updates than state-of-the-art methods while maintaining competitive query performance.

1. Introduction

A reachability query $q(u, v)$ determines if a path exists from vertex $u$ to vertex $v$. While efficient for static graphs, real-world networks like social media and transit systems are inherently dynamic. The primary hurdle in scaling these queries is the "DAG maintenance bottleneck." Updating a DAG after a single edge insertion can take significantly longer than processing millions of queries. DBL addresses this by avoiding DAG maintenance entirely, focusing instead on a labeling strategy that handles updates locally and efficiently.

2. Methodology: The DBL Framework

DBL employs a two-pronged indexing strategy to cover the query space effectively. The framework is designed to handle "yes" answers through landmarks and "no" answers through leaf-node pruning.

2.1 Dynamic Landmark (DL) Labels

DL labels target high-centrality vertices, known as landmarks. Each vertex $v$ maintains two sets: $DL_{in}(v)$, containing landmarks that can reach $v$, and $DL_{out}(v)$, containing landmarks reachable from $v$. If $DL_{out}(u) \cap DL_{in}(v) \neq \emptyset$, then $u$ can reach $v$. This provides a fast "hit" for many reachable pairs.

2.2 Bidirectional Leaf (BL) Labels

To handle unreachable pairs, DBL uses leaf nodes (vertices with zero in-degree or out-degree). BL labels store hash values of reachable/reaching leaf nodes. If the required leaf nodes for $v$ are not reachable from $u$ (checked via hash sets), the query can be immediately pruned as "unreachable."

Figure 1: Illustration of Graph G alongside its corresponding DL and BL labels. The labels provide a compact representation of reachability information without requiring a DAG.

2.3 Pruned Search and Updates

When labels are inconclusive, DBL falls back to a Breadth-First Search (BFS). However, the search space is significantly reduced by using the DL and BL labels as pruning rules. For updates, DBL uses a pruned BFS to update only the labels of affected nodes, avoiding the global re-computation of SCCs. The notation used in these operations is detailed in Table 1.

Table 1: Summary of notations and descriptions used in the DBL indexing and query framework.

3. Experimental Evaluation

The authors evaluated DBL on eight diverse datasets, including social networks (LiveJournal, Twitter) and web graphs (BerkStan).

3.1 Performance and Scalability

DBL demonstrated orders of magnitude speedup in index maintenance compared to DAG-based methods like DAGGER and TOL. In terms of query latency, DBL processed 1 million queries in sub-second time (e.g., 108ms for LiveJournal). The framework also showed excellent parallel scaling using OpenMP and CUDA, with the GPU implementation (DBL-G) providing significant acceleration on dense graphs.

3.2 Label Effectiveness

A key finding was the high coverage of the labeling system. In several datasets, the combination of DL and BL labels answered over 99% of queries directly, minimizing the need for the BFS fallback.

4. Conclusion

DBL represents a significant shift in dynamic reachability indexing by removing the DAG maintenance bottleneck. Its complementary use of landmarks and leaf nodes provides a robust balance between update efficiency and query speed. Future work will explore extending DBL to handle frequent edge deletions through more advanced "lazy update" mechanisms.

Summary updated

BibTeX
@inproceedings{lyu2021dbl,
  author = {Qiuyi Lyu and Yuchen Li and Bingsheng He and Bin Gong},
  title = {{DBL: Efficient Reachability Queries on Dynamic Graphs (Complete Version)}},
  booktitle = {DASFAA},
  year = {2021},
  doi = {10.1007/978-3-030-73197-7\_52},
}
Figure