How Fast Can You Update Your MST?
How Fast Can You Update Your MST?
复制标题
您更新 MST 的速度有多快？
DOI：
10.1145/3350755.3400240
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
L. Li
中科院分区：
文献类型：
--
作者：
Seth Gilbert;L. Li
想象一个由计算机集群处理的大型图，例如，由k机模型或大规模并行计算模型描述。然而，这个图不是静态的;相反，它正在接收不断的更新流。群集处理更新流的速度有多快？在本文中，我们想问的基本问题是，我们是否可以足够快地更新图，以跟上流。我们专注于维护最小生成树（MST）的问题，我们给出了一个算法的k机模型，可以处理O（k）图更新每O（1）轮的高概率。(And这些结果延续到大规模并行计算（MPC）模型。我们还展示了一个下界，即，在O（1）轮中处理k1+ε更新是不可能的。因此，我们提供了一个近乎严密的答案，一个集群可以多快地响应流的图形修改，同时保持MST的问题。
Imagine a large graph that is being processed by a cluster of computers, e.g., described by the k-machine model or the Massively Parallel Computation Model. The graph, however, is not static; instead it is receiving a constant stream of updates. How fast can the cluster process the stream of updates? The fundamental question we want to ask in this paper is whether we can update the graph fast enough to keep up with the stream. We focus specifically on the problem of maintaining a minimum spanning tree (MST), and we give an algorithm for the k-machine model that can process O(k) graph updates per O(1) rounds with high probability. (And these results carry over to the Massively Parallel Computation (MPC) model.) We also show a lower bound, i.e., it is impossible to process k1+ε updates in O(1) rounds. Thus we provide a nearly tight answer to the question of how fast a cluster can respond to a stream of graph modifications while maintaining an MST.