文章基本信息

标题：Brief Announcement: Massively Parallel Approximate Distance Sketches
本地全文：下载
作者：Michael Dinitz ; Yasamin Nazari
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：146
页码：1-3
DOI：10.4230/LIPIcs.DISC.2019.42
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 Elkin and Neiman (2016). 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.
关键词：Distance Sketches; Massively Parallel Computation; Congested Clique