Massively Parallel Algorithms for Large-Scale Graph Problems

Project Details

Description

Due to the growth of datasets, processing them centrally on a single computer has become untenably inefficient or even impossible. Hence, there is an urgent demand for distributed and parallel approaches for data processing. To help with designing algorithms for processing big data, many large-scale computing frameworks, such as MapReduce, Hadoop, Dryad, and Spark have emerged. In this project, we study the theoretical foundations of these frameworks to be able to design more efficient algorithms and to understand their limitations. The goal of the project is to understand what can be computed by these frameworks. Through a mathematical model abstracting these frameworks, we, on the one hand, show how to solve fundamental problems efficiently, and on the other hand, identify problems that are provably hard. Ideally, this allows us to understand how the practical frameworks need to be adjusted to provide more efficient data processing.
Acronym-
StatusActive
Effective start/end date01/09/202031/08/2024

Collaborative partners

Fingerprint

Explore the research topics touched on by this project. These labels are generated based on the underlying awards/grants. Together they form a unique fingerprint.
  • Adaptive Massively Parallel Connectivity in Optimal Space

    Latypov, R., Łacki, J., Maus, Y. & Uitto, J., 17 Jun 2023, SPAA 2023 - Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures. ACM, p. 431-441 11 p.

    Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingsScientificpeer-review

    Open Access
    File
    9 Downloads (Pure)
  • Conditionally Optimal Parallel Coloring of Forests

    Grunau, C., Latypov, R., Maus, Y., Pai, S. & Uitto, J., Oct 2023, 37th International Symposium on Distributed Computing, DISC 2023. Oshman, R. (ed.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 23. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 281).

    Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingsScientificpeer-review

    Open Access
    File
    9 Downloads (Pure)
  • Distributed Symmetry Breaking on Power Graphs via Sparsification

    Maus, Y., Peltonen, S. & Uitto, J., 19 Jun 2023, PODC 2023 - Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing. ACM, p. 157-167 11 p.

    Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingsScientificpeer-review

    Open Access
    File
    1 Citation (Scopus)
    9 Downloads (Pure)