Answering Reachability Queries on Incrementally Updated Graphs by Hierarchical Labeling Schema
Tak-Lam, Wong · Acta Scientiarum Naturalium Universitatis Sunyatseni · 2016
我们建议一个新奇答案纲要叫了层次标记纲要(HLS ) 在指导的图回答 reachability 询问。与集中于静态的指导的非循环的图(DAG ) 的许多存在途径不同，我们的纲要集中于顶点或弧能逐渐地被加到一张图的指导的周期的图(DCG ) 。不同于许多传统的途径， HLS 不要求图在构造它的索引非循环。因此，事实上，它能被用于 DAG 和 DCG。当顶点或弧被加到一张图时， HLS 能够逐渐地更新这个索引而不是每次从擦伤重新计算这个索引，使它比在实践的许多另外的途径更有效。HLS 的基本想法是在一张图为每个顶点创造一棵树并且一起连接树以便每当二个顶点被给时，我们能立即知道是否由指适当的树在他们之间有一条路径。我们在两个上进行了广泛的实验真实世界的数据集和综合数据集。我们比较了 HLS 的性能，以索引构造时间，询问处理时空消费与二最先进的方法论，路径树方法和 3-hop 方法。当一张图逐渐地被更新时，我们也进行了模拟为状况建模。对静态的图上的 HLS 的不同算法的表演比较也被学习了。我们的结果证明 HLS 在实践是高度有竞争力的并且在图经常被更新的情况中是特别地有用的。