Brief Announcement: Massively Parallel Approximate Distance Sketches
Brief Announcement: Massively Parallel Approximate Distance Sketches
复制标题
简短公告：大规模并行近似距离草图
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Yasamin Nazari
中科院分区：
文献类型：
--
作者：
M. Dinitz;Yasamin Nazari
允许有效距离估计的数据结构已经在集中式模型和经典分布式模型中得到了广泛的研究。我们开始研究更新的（并且可以说更现实的）分布式计算模型：拥塞集团模型和大规模并行计算（MPC）模型。在 MPC 中，我们给出了两个主要结果：一种构造拉伸/空间最佳距离草图但需要（小的）多项式轮次的算法，以及一种构造具有更差拉伸的距离草图但只需要多对数轮次的算法。在此过程中，我们展示了其他有用的组合结构也可以在 MPC 中计算。特别是，我们使用的一个关键组件是 [2] 的跳集的 MPC 构造。该结果具有其他应用，例如用于低内存 MPC 设置中加权图的恒定近似单源最短路径的第一个多对数时间算法。 2012 ACM 学科分类 计算理论 → 大规模并行算法
Data structures that allow efficient distance estimation have been extensively studied both in centralized models and classical distributed models. We initiate their study in newer (and arguably more realistic) models of distributed computation: the Congested Clique model and the Massively Parallel Computation (MPC) model. In MPC we give two main results: an algorithm that constructs stretch/space optimal distance sketches but takes a (small) polynomial number of rounds, and an algorithm that constructs distance sketches with worse stretch but that only takes polylogarithmic rounds. Along the way, we show that other useful combinatorial structures can also be computed in MPC. In particular, one key component we use is an MPC construction of the hopsets of [2]. This result has additional applications such as the first polylogarithmic time algorithm for constant approximate single-source shortest paths for weighted graphs in the low memory MPC setting. 2012 ACM Subject Classification Theory of computation → Massively parallel algorithms