Document Open Access Logo

Massively Parallel Approximate Distance Sketches

Authors Michael Dinitz, Yasamin Nazari

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2019.35.pdf
  • Filesize: 0.5 MB
  • 17 pages

Document Identifiers

Author Details

Michael Dinitz
  • Johns Hopkins University, Baltimore, MD, United States
Yasamin Nazari
  • Johns Hopkins University, Baltimore, MD, United States

Funding

This work supported is in part by NSF awards CCF-1464239 and CCF-1909111.

Acknowledgements

The authors are thankful to Goran Zuzic for helpful discussions.

Cite AsGet BibTex

Michael Dinitz and Yasamin Nazari. Massively Parallel Approximate Distance Sketches. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 35:1-35:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.OPODIS.2019.35

Abstract

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 [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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Massively parallel algorithms
Keywords
  • Distance Sketches
  • Massively Parallel Computation
  • Distance Oracles
  • Single-Source Shortest Paths

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Alexandr Andoni, Zhao Song, Clifford Stein, Zhengyu Wang, and Peilin Zhong. Parallel graph connectivity in log diameter rounds. In Proceedings of the Symposium on Foundations of Computer Science (FOCS). IEEE, 2018. Google Scholar
  2. Surender Baswana and Sandeep Sen. A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Structures & Algorithms, 30(4):532-563, 2007. Google Scholar
  3. Paul Beame, Paraschos Koutris, and Dan Suciu. Communication steps for parallel query processing. In Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGAI symposium on Principles of database systems, pages 273-284. ACM, 2013. Google Scholar
  4. Ruben Becker, Andreas Karrenbauer, Sebastian Krinninger, and Christoph Lenzen. Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models. In LIPIcs-Leibniz International Proceedings in Informatics, volume 91. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  5. Soheil Behnezhad, Mahsa Derakhshan, and MohammadTaghi Hajiaghayi. Brief Announcement: Semi-MapReduce Meets Congested Clique. arXiv preprint arXiv:1802.10297, 2018. Google Scholar
  6. Keren Censor-Hillel, Michal Dory, Janne H Korhonen, and Dean Leitersdorf. Fast Approximate Shortest Paths in the Congested Clique. In Proceedings of Symposium on Principles of Distributed Computing. ACM, 2019. Google Scholar
  7. Shiri Chechik. Approximate distance oracles with constant query time. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing (STOC), pages 654-663. ACM, 2014. Google Scholar
  8. Edith Cohen. Polylog-time and near-linear work approximation scheme for undirected shortest paths. Journal of the ACM (JACM), 47(1):132-166, 2000. Google Scholar
  9. Michael Elkin and Ofer Neiman. Hopsets with constant hopbound, and applications to approximate shortest paths. In Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on, pages 128-137. IEEE, 2016. Google Scholar
  10. Michael Elkin and Ofer Neiman. On efficient distributed construction of near optimal routing schemes. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, pages 235-244. ACM, 2016. Google Scholar
  11. Stephan Friedrichs and Christoph Lenzen. Parallel metric tree embedding based on an algebraic view on moore-bellman-ford. Journal of the ACM (JACM), 65(6):43, 2018. Google Scholar
  12. Michael T Goodrich, Nodari Sitchinava, and Qin Zhang. Sorting, searching, and simulation in the mapreduce framework. In International Symposium on Algorithms and Computation, pages 374-383. Springer, 2011. Google Scholar
  13. MohammadTaghi Hajiaghayi, Silvio Lattanzi, Saeed Seddighin, and Cliff Stein. MapReduce Meets Fine-Grained Complexity: MapReduce Algorithms for APSP, Matrix Multiplication, 3-SUM, and Beyond. arXiv preprint arXiv:1905.01748, 2019. Google Scholar
  14. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 489-498. ACM, 2016. Google Scholar
  15. Howard Karloff, Siddharth Suri, and Sergei Vassilvitskii. A model of computation for MapReduce. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 938-948. SIAM, 2010. Google Scholar
  16. Hartmut Klauck, Danupon Nanongkai, Gopal Pandurangan, and Peter Robinson. Distributed computation of large-scale graph problems. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, pages 391-410. Society for Industrial and Applied Mathematics, 2015. Google Scholar
  17. Christoph Lenzen and Boaz Patt-Shamir. Fast routing table construction using small messages. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 381-390. ACM, 2013. Google Scholar
  18. Zvi Lotker, Boaz Patt-Shamir, Elan Pavlov, and David Peleg. Minimum-weight spanning tree construction in O (log log n) communication rounds. SIAM Journal on Computing, 35(1):120-131, 2005. Google Scholar
  19. Manor Mendel and Assaf Naor. Ramsey partitions and proximity data structures. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 109-118. IEEE, 2006. Google Scholar
  20. Mihai Patrascu and Liam Roditty. Distance Oracles beyond the Thorup-Zwick Bound. SIAM Journal on Computing, 43(1):300-311, 2014. Google Scholar
  21. Mihai Patrascu, Liam Roditty, and Mikkel Thorup. A new infinity of distance oracles for sparse graphs. In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 738-747. IEEE, 2012. Google Scholar
  22. D. Peleg. Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, 2000. URL: https://doi.org/10.1137/1.9780898719772.
  23. Tim Roughgarden, Sergei Vassilvitskii, and Joshua R Wang. Shuffles and circuits (on lower bounds for modern parallel computation). Journal of the ACM (JACM), 65(6):41, 2018. Google Scholar
  24. Atish Das Sarma, Michael Dinitz, and Gopal Pandurangan. Efficient distributed computation of distance sketches in networks. Distributed Computing, 28(5):309-320, 2015. Google Scholar
  25. Mikkel Thorup and Uri Zwick. Approximate distance oracles. Journal of the ACM (JACM), 52(1):1-24, 2005. Google Scholar
  26. Christian Wulff-Nilsen. Approximate distance oracles with improved query time. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 539-549. SIAM, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact