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.
翻译:由于图表在许多应用中经常更新,因此必须支持高效的图形更新,同时在可获取性查询方面提供良好的绩效。现有解决方案压缩了原图,并配有定向环形图(DAG),提出了高效的查询处理和索引更新技术。然而,这些解决方案侧重于优化“强连成构件”保持不变的情景,并忽略了在更新SCC时DAG维护费用过高。我们在本文件中建议DBL,即高效的DBL,即一个高效的DAG-无DAG索引,用于支持动态图形的可访问性查询,同时提供仅插入式更新。DBL建立于两个补充指数:动态Landmark标签和双向Leaf标签。前两个指标利用里程碑节点快速确定可实现的配对,而后一对则无法实现的配对,通过在图表中为叶节点编制索引。我们根据动态可获取性DBLL, 与动态可获取性可达性指数的状态方法评估,同时在现实世界数据设置的级别更新中进行大规模实验。