TY - GEN
T1 - Massively parallel approximate distance sketches
AU - Dinitz, Michael
AU - Nazari, Yasamin
PY - 2020/2/1
Y1 - 2020/2/1
N2 - Data structures that allow efficient distance estimation (distance oracles, distance sketches, etc.) have been extensively studied, and are particularly well studied in centralized models and classical distributed models such as CONGEST. 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. We provide efficient constructions in both of these models, but our core results are for MPC. 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 to construct distance sketches are an MPC construction of the hopsets of [9]. 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.
AB - Data structures that allow efficient distance estimation (distance oracles, distance sketches, etc.) have been extensively studied, and are particularly well studied in centralized models and classical distributed models such as CONGEST. 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. We provide efficient constructions in both of these models, but our core results are for MPC. 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 to construct distance sketches are an MPC construction of the hopsets of [9]. 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.
UR - http://www.scopus.com/inward/record.url?scp=85081175694&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.OPODIS.2019.35
DO - 10.4230/LIPIcs.OPODIS.2019.35
M3 - Conference contribution
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 23rd International Conference on Principles of Distributed Systems, OPODIS 2019
A2 - Felber, P.
A2 - Friedman, R.
A2 - Gilbert, S.
A2 - Miller, A.
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 23rd International Conference on Principles of Distributed Systems, OPODIS 2019
Y2 - 17 December 2019 through 19 December 2019
ER -