  Reachability query is a fundamental problem on graphs, which has been
extensively studied in academia and industry. Since graphs are subject to
frequent updates in many applications, it is essential to support efficient
graph updates while offering good performance in reachability queries. Existing
solutions compress the original graph with the Directed Acyclic Graph (DAG) and
propose efficient query processing and index update techniques. However, they
focus on optimizing the scenarios where the Strong Connected Components(SCCs)
remain unchanged and have overlooked the prohibitively high cost of the DAG
maintenance when SCCs are updated. In this paper, we propose DBL, an efficient
DAG-free index to support the reachability query on dynamic graphs with
insertion-only updates. DBL builds on two complementary indexes: Dynamic
Landmark (DL) label and Bidirectional Leaf (BL) label. The former leverages
landmark nodes to quickly determine reachable pairs whereas the latter prunes
unreachable pairs by indexing the leaf nodes in the graph. We evaluate DBL
against the state-of-the-art approaches on dynamic reachability index with
extensive experiments on real-world datasets. The results have demonstrated
that DBL achieves orders of magnitude speedup in terms of index update, while
still producing competitive query efficiency.
