论文标题
在大规模并行计算模型中具有批处理更新的动态图算法
Dynamic Graph Algorithms with Batch Updates in the Massively Parallel Computation Model
论文作者
论文摘要
我们研究了大量并联计算模型中的动态图算法，该算法的灵感来自实际数据处理系统。我们的目标是提供可以有效处理大量边缘插入和删除的算法。 我们展示的算法需要更少的回合来将解决方案更新到诸如最小跨越森林，2码连接的组件和最大匹配等问题之类的问题，而其静态对应物要求从头开始对其进行计算。它们在最限制的内存制度中起作用，其中每台机器的本地内存在图形顶点的数量中具有强烈的倍率。在稀疏图上已知的静态算法的圆形复杂性上，他们可以有效处理的批次大小会改善。 我们的算法可以处理尺寸$θ（s）$的更新，对于最小跨越森林和2边缘连接的组件，以及$θ（s^{1- \ varepsilon}）$，用于最大匹配，以$ o（1）$（1）$回合，其中$ S $是单个机器的本地记忆。
We study dynamic graph algorithms in the Massively Parallel Computation model, which was inspired by practical data processing systems. Our goal is to provide algorithms that can efficiently handle large batches of edge insertions and deletions. We show algorithms that require fewer rounds to update a solution to problems such as Minimum Spanning Forest, 2-Edge Connected Components, and Maximal Matching than would be required by their static counterparts to compute it from scratch. They work in the most restrictive memory regime, in which local memory per machine is strongly sublinear in the number of graph vertices. Improving on the size of the batch they can handle efficiently would improve on the round complexity of known static algorithms on sparse graphs. Our algorithms can process batches of updates of size $Θ(S)$, for Minimum Spanning Forest and 2-Edge Connected Components, and $Θ(S^{1-\varepsilon})$, for Maximal Matching, in $O(1)$ rounds, where $S$ is the local memory of a single machine.
