论文标题
batchhl：在批处理网络上回答距离查询
BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale
论文作者
论文摘要
许多现实世界的应用程序都在动态图上运行，随着时间的流逝，其拓扑结构的快速变化。但是，设计能够有效支持此类图更改的动态算法是具有挑战性的。为了应对挑战，我们提出了一个用于回答距离查询的动态框架，该框架结合了离线标签和在线搜索，以利用双方的优势 - 通过有限的尺寸，但为在线搜索提供了良好的近似值来加速查询处理。我们设计批处理算法以有效地动态距离标记，以反映基础图上的批处理更新。除了提供理论分析以确定正确性，标记最小性和计算复杂性外，我们还对14个现实世界网络进行了实验，以经验验证所提出算法的效率和可扩展性。
Many real-world applications operate on dynamic graphs that undergo rapid changes in their topological structure over time. However, it is challenging to design dynamic algorithms that are capable of supporting such graph changes efficiently. To circumvent the challenge, we propose a batch-dynamic framework for answering distance queries, which combines offline labelling and online searching to leverage the advantages from both sides - accelerating query processing through a partial distance labelling that is of limited size but provides a good approximation to bound online searches. We devise batch-dynamic algorithms to dynamize a distance labelling efficiently in order to reflect batch updates on the underlying graph. In addition to providing theoretical analysis for the correctness, labelling minimality, and computational complexity, we have conducted experiments on 14 real-world networks to empirically verify the efficiency and scalability of the proposed algorithms.
