Document Open Access Logo

Adaptive Massively Parallel Constant-Round Tree Contraction

Authors MohammadTaghi Hajiaghayi, Marina Knittel, Hamed Saleh, Hsin-Hao Su

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.83.pdf
  • Filesize: 1.25 MB
  • 23 pages

Document Identifiers

Author Details

MohammadTaghi Hajiaghayi
  • University of Maryland, College Park, MD, USA
Marina Knittel
  • University of Maryland, College Park, MD, USA
Hamed Saleh
  • University of Maryland, College Park, MD, USA
Hsin-Hao Su
  • Boston College, MA, USA

Funding

  • Hajiaghayi, MohammadTaghi: Supported by the NSF BIGDATA Grant No. 1546108, NSF SPX Grant No. 1822738, and NSF AF Grant No. 2114269.
  • Knittel, Marina: Supported by the NSF BIGDATA Grant No. 1546108, NSF SPX Grant No. 1822738, ARCS Endowment Award, and Ann G. Wylie Fellowship.
  • Su, Hsin-Hao: Supported by NSF Grant No. CCF-2008422.

Cite AsGet BibTex

MohammadTaghi Hajiaghayi, Marina Knittel, Hamed Saleh, and Hsin-Hao Su. Adaptive Massively Parallel Constant-Round Tree Contraction. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 83:1-83:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ITCS.2022.83

Abstract

Miller and Reif’s FOCS'85 [Gary L. Miller and John H. Reif, 1989] classic and fundamental tree contraction algorithm is a broadly applicable technique for the parallel solution of a large number of tree problems. Additionally it is also used as an algorithmic design technique for a large number of parallel graph algorithms. In all previously explored models of computation, however, tree contractions have only been achieved in Ω(log n) rounds of parallel run time. In this work, we not only introduce a generalized tree contraction method but also show it can be computed highly efficiently in O(1/ε³) rounds in the Adaptive Massively Parallel Computing (AMPC) setting, where each machine has O(n^ε) local memory for some 0 < ε < 1. AMPC is a practical extension of Massively Parallel Computing (MPC) which utilizes distributed hash tables [MohammadHossein Bateni et al., 2017; Behnezhad et al., 2019; Raimondas Kiveris et al., 2014]. In general, MPC is an abstract model for MapReduce, Hadoop, Spark, and Flume which are currently widely used across industry and has been studied extensively in the theory community in recent years. Last but not least, we show that our results extend to multiple problems on trees, including but not limited to maximum and maximal matching, maximum and maximal independent set, tree isomorphism testing, and more.

Subject Classification

ACM Subject Classification
  • Theory of computation → Massively parallel algorithms
Keywords
  • Adaptive Massively Parallel Computation
  • Tree Contraction
  • Matching
  • Independent Set
  • Tree Isomorphism

Metrics

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

Related Versions

References

  1. Umut A. Acar, Guy E. Blelloch, Robert Harper, Jorge L. Vittes, and Shan Leung Maverick Woo. Dynamizing static algorithms, with applications to dynamic trees and history independence. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete, pages 531-540, 2004. Google Scholar
  2. Kook Jin Ahn and Sudipto Guha. Access to data and number of iterations: Dual primal algorithms for maximum matching under resource constraints. In Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms, pages 202-211, 2015. Google Scholar
  3. Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, and Grigory Yaroslavtsev. Parallel algorithms for geometric graph problems. In Symposium on Theory of Computing, pages 574-583. ACM, 2014. Google Scholar
  4. Alexandr Andoni, Zhao Song, Clifford Stein, Zhengyu Wang, and Peilin Zhong. Parallel graph connectivity in log diameter rounds. In 59th IEEE Annual Symposium on Foundations of Computer Science, pages 674-685. IEEE Computer Society, 2018. Google Scholar
  5. Alexandr Andoni, Clifford Stein, and Peilin Zhong. Log diameter rounds algorithms for 2-vertex and 2-edge connectivity. In 46th International Colloquium on Automata, Languages, and Programming, pages 14:1-14:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  6. Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab S. Mirrokni, and Cliff Stein. Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete, pages 1616-1635, 2019. Google Scholar
  7. Sepehr Assadi, Yu Chen, and Sanjeev Khanna. Sublinear algorithms for δ+1 vertex coloring. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete, pages 767-786, 2019. Google Scholar
  8. Sepehr Assadi, Xiaorui Sun, and Omri Weinstein. Massively parallel algorithms for finding well-connected components in sparse graphs. In Proceedings of the 2019 ACM Symposium on Principles of Distributed, pages 461-470, 2019. Google Scholar
  9. Mikhail J. Atallah, S. Rao Kosaraju, Lawrence L. Larmore, Gary L. Miller, and Shang-Hua Teng. Constructing trees in parallel. In Proceedings of the ACM Symposium on Parallel Algorithms and Architectures, 1989. Google Scholar
  10. MohammadHossein Bateni, Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Raimondas Kiveris, Silvio Lattanzi, and Vahab S. Mirrokni. Affinity clustering: Hierarchical clustering at scale. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems, pages 6864-6874, 2017. Google Scholar
  11. MohammadHossein Bateni, Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, and Vahab S. Mirrokni. Brief announcement: Mapreduce algorithms for massive trees. In 45th International Colloquium on Automata, Languages, and Programming, pages 162:1-162:4, 2018. Google Scholar
  12. MohammadHossein Bateni, Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, and Vahab S. Mirrokni. Massively parallel dynamic programming on trees. CoRR, 2018. Google Scholar
  13. Soheil Behnezhad. Time-optimal sublinear algorithms for matching and vertex cover. arXiv preprint arXiv:2106.02942, 2021. Google Scholar
  14. Soheil Behnezhad, Sebastian Brandt, Mahsa Derakhshan, Manuela Fischer, MohammadTaghi Hajiaghayi, Richard M Karp, and Jara Uitto. Massively parallel computation of matching and mis in sparse graphs. In ACM SIGACT, pages 481-490, 2019. Google Scholar
  15. Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Marina Knittel, and Hamed Saleh. Streaming and massively parallel algorithms for edge coloring. In 27th Annual European Symposium on Algorithms, pages 15:1-15:14, 2019. Google Scholar
  16. Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Łacki, Vahab Mirrokni, and Warren Schudy. Massively parallel computation via remote memory access. In The 31st ACM Symposium on Parallelism in Algorithms and Architectures, pages 59-68, 2019. Google Scholar
  17. Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Lacki, and Vahab S. Mirrokni. Near-optimal massively parallel graph connectivity. In 60th IEEE Annual Symposium on Foundations of Computer Science, pages 1615-1636, 2019. Google Scholar
  18. Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Lacki, Vahab S. Mirrokni, and Warren Schudy. Parallel graph algorithms in constant adaptive rounds: Theory meets practice. Proc. VLDB Endow., pages 3588-3602, 2020. Google Scholar
  19. Soheil Behnezhad, MohammadTaghi Hajiaghayi, and David G. Harris. Exponentially faster massively parallel maximal matching. In 60th IEEE Annual Symposium on Foundations of Computer Science, pages 1637-1649, 2019. Google Scholar
  20. Hans L. Bodlaender, Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michal Pilipczuk. A c^kn 5-approximation algorithm for treewidth. SIAM J. Comput., pages 317-378, 2016. Google Scholar
  21. Hans L. Bodlaender and Torben Hagerup. Parallel algorithms with optimal speedup for bounded treewidth. In Zoltán Fülöp and Ferenc Gécseg, editors, Automata, Languages and Programming, 22nd International Colloquium, ICALP95, Szeged, Hungary, July 10-14, 1995, Proceedings, volume 944 of Lecture Notes in Computer Science, pages 268-279. Springer, 1995. Google Scholar
  22. Mahdi Boroujeni, Soheil Ehsani, Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, and Saeed Seddighin. Approximating edit distance in truly subquadratic time: Quantum and mapreduce. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete, pages 1170-1189, 2018. Google Scholar
  23. Craig Chambers, Ashish Raniwala, Frances Perry, Stephen Adams, Robert R. Henry, Robert Bradshaw, and Nathan Weizenbaum. Flumejava: easy, efficient data-parallel pipelines. In Benjamin G. Zorn and Alexander Aiken, editors, Proceedings of the 2010 ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 363-375, 2010. Google Scholar
  24. Moses Charikar, Weiyun Ma, and Li-Yang Tan. Unconditional lower bounds for adaptive massively parallel computation. In SPAA '20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures, pages 141-151, 2020. Google Scholar
  25. Richard Cole and Uzi Vishkin. The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time. Algorithmica, pages 329-346, 1988. Google Scholar
  26. Artur Czumaj, Jakub Lacki, Aleksander Madry, Slobodan Mitrovic, Krzysztof Onak, and Piotr Sankowski. Round compression for parallel matching algorithms. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory, pages 471-484, 2018. Google Scholar
  27. Eliezer Dekel, Simeon Ntafos, and Shie-Tung Peng. Parallel tree techniques and code optimization. In Filia Makedon, Kurt Mehlhorn, T. Papatheodorou, and P. Spirakis, editors, VLSI Algorithms and Architectures, pages 205-216, 1986. Google Scholar
  28. Apache Software Foundation. Hadoop. https://hadoop.apache.org/. Google Scholar
  29. H. Gazit, Gary L. Miller, and ShangHua Teng. Optimal tree contraction in an EREW model. In Concurrent Computations: Algorithms, Architecture and Technology, pages 139-156, 1988. Google Scholar
  30. Hillel Gazit and Gary L. Miller. A parallel algorithm for finding a separator in planar graphs. In 28th Annual Symposium on Foundations of Computer Science, pages 238-248, 1987. Google Scholar
  31. Mohsen Ghaffari, Themis Gouleakis, Christian Konrad, Slobodan Mitrovic, and Ronitt Rubinfeld. Improved massively parallel computation algorithms for mis, matching, and vertex cover. In Proceedings of the 2018 ACM Symposium on Principles of Distributed, pages 129-138, 2018. Google Scholar
  32. Mohsen Ghaffari, Christoph Grunau, and Ce Jin. Improved mpc algorithms for mis, matching, and coloring on trees and beyond. arXiv preprint arXiv:2002.09610, 2020. Google Scholar
  33. Mohsen Ghaffari, Fabian Kuhn, and Jara Uitto. Conditional hardness results for massively parallel computation from distributed lower bounds. In 60th IEEE Annual Symposium on Foundations of Computer Science, pages 1650-1663, 2019. Google Scholar
  34. Mohsen Ghaffari and Jara Uitto. Sparsifying distributed algorithms with ramifications in massively parallel computation and centralized local computation. In SODA, pages 1636-1653. SIAM, 2019. Google Scholar
  35. Alan Gibbons and Wojciech Rytter. Optimal parallel algorithms for dynamic expression evaluation and context-free recognition. Inf. Comput., pages 32-45, 1989. Google Scholar
  36. Michael T. Goodrich and S. Rao Kosaraju. Sorting on a parallel pointer machine with applications to set expression evaluation. J. ACM, pages 331-361, 1996. Google Scholar
  37. Martin Grohe and Oleg Verbitsky. Testing graph isomorphism in parallel by playing a game. In Automata, Languages and Programming, 33rd International Colloquium, pages 3-14, 2006. Google Scholar
  38. MohammadTaghi Hajiaghayi and Marina Knittel. Matching affinity clustering: Improved hierarchical clustering at scale with guarantees. In Proceedings of the 19th International Conference on Autonomous Agents, pages 1864-1866, 2020. Google Scholar
  39. MohammadTaghi Hajiaghayi, Hamed Saleh, Saeed Seddighin, and Xiaorui Sun. String matching with wildcards in the massively parallel computation model. In SPAA, pages 275-284, 2021. Google Scholar
  40. MohammadTaghi Hajiaghayi, Saeed Seddighin, and Xiaorui Sun. Massively parallel approximation algorithms for edit distance and longest common subsequence. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1654-1672. SIAM, 2019. Google Scholar
  41. Nicholas J. A. Harvey, Christopher Liaw, and Paul Liu. Greedy and local ratio algorithms in the mapreduce model. In Proceedings of the 30th on Symposium on Parallelism in Algorithms, pages 43-52, 2018. Google Scholar
  42. Artur Jez and Markus Lohrey. Approximation of smallest linear tree grammar. Inf. Comput., pages 215-251, 2016. Google Scholar
  43. Howard J. 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, 2010. Google Scholar
  44. Raimondas Kiveris, Silvio Lattanzi, Vahab S. Mirrokni, Vibhor Rastogi, and Sergei Vassilvitskii. Connected components in mapreduce and beyond. In Proceedings of the ACM Symposium on Cloud Computing, pages 18:1-18:13, 2014. Google Scholar
  45. Jakub Lacki, Slobodan Mitrovic, Krzysztof Onak, and Piotr Sankowski. Walking randomly, massively, and efficiently. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory, pages 364-377, 2020. Google Scholar
  46. Gary L. Miller and Vijaya Ramachandran. A new graph triconnectivity algorithm and its parallelization. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing, pages 335-344, 1987. Google Scholar
  47. Gary L. Miller, Vijaya Ramachandran, and Erich Kaltofen. Efficient parallel evaluation of straight-line code and arithmetic circuits. SIAM J. Comput., pages 687-695, 1988. Google Scholar
  48. Gary L. Miller and John H. Reif. Parallel tree contraction and its application. In 26th Annual Symposium on Foundations of Computer Science, pages 478-489, 1985. Google Scholar
  49. Gary L. Miller and John H. Reif. Parallel tree contraction part 1: Fundamentals. Adv. Comput. Res., pages 47-72, 1989. Google Scholar
  50. Gary L. Miller and John H. Reif. Parallel tree contraction, part 2: Further applications. SIAM J. Comput., pages 1128-1147, 1991. Google Scholar
  51. Danupon Nanongkai and Michele Scquizzato. Equivalence classes and conditional hardness in massively parallel fcomputations. In 23rd International Conference on Principles of Distributed Systems, pages 33:1-33:16, 2019. Google Scholar
  52. Dimitrios Papadopoulos, Charalampos Papamanthou, Roberto Tamassia, and Nikos Triandopoulos. Practical authenticated pattern matching with optimal proof size. Proc. VLDB Endow., pages 750-761, 2015. Google Scholar
  53. Tim Roughgarden, Sergei Vassilvitskii, and Joshua R. Wang. Shuffles and circuits: (on lower bounds for modern parallel computation). In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms, pages 1-12, 2016. Google Scholar
  54. Grigory Yaroslavtsev and Adithya Vadapalli. Massively parallel algorithms and hardness for single-linkage clustering under 𝓁_p distances. In Proceedings of the 35th International Conference on Machine Learning, pages 5596-5605, 2018. Google Scholar
  55. Matei Zaharia, Reynold S. Xin, Patrick Wendell, Tathagata Das, Michael Armbrust, Ankur Dave, Xiangrui Meng, Josh Rosen, Shivaram Venkataraman, Michael J. Franklin, Ali Ghodsi, Joseph Gonzalez, Scott Shenker, and Ion Stoica. Apache spark: a unified engine for big data processing. Commun. ACM, pages 56-65, 2016. 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