License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2018.162
URN: urn:nbn:de:0030-drops-91666
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9166/
Bateni, MohammadHossein ;
Behnezhad, Soheil ;
Derakhshan, Mahsa ;
Hajiaghayi, MohammadTaghi ;
Mirrokni, Vahab
Brief Announcement: MapReduce Algorithms for Massive Trees
Abstract
Solving large-scale graph problems is a fundamental task in many real-world applications, and it is an increasingly important problem in data analysis. Despite the large effort in designing scalable graph algorithms, many classic graph problems lack algorithms that require only a sublinear number of machines and space in the input size. Specifically when the input graph is large and sparse, which is indeed the case for many real-world graphs, it becomes impossible to store and access all the vertices in one machine - something that is often taken for granted in designing algorithms for massive graphs. The theoretical model that we consider is the Massively Parallel Communications (MPC) model which is a popular theoretical model of MapReduce-like systems. In this paper, we give an algorithmic framework to adapt a large family of dynamic programs on MPC. We start by introducing two classes of dynamic programming problems, namely "(poly log)-expressible" and "linear-expressible" problems. We show that both classes can be solved efficiently using a sublinear number of machines and a sublinear memory per machine. To achieve this result, we introduce a series of techniques that can be plugged together. To illustrate the generality of our framework, we implement in O(log n) rounds of MPC, the dynamic programming solution of fundamental problems such as minimum bisection, k-spanning tree, maximum independent set, longest path, etc., when the input graph is a tree.
BibTeX - Entry
@InProceedings{bateni_et_al:LIPIcs:2018:9166,
author = {MohammadHossein Bateni and Soheil Behnezhad and Mahsa Derakhshan and MohammadTaghi Hajiaghayi and Vahab Mirrokni},
title = {{Brief Announcement: MapReduce Algorithms for Massive Trees}},
booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
pages = {162:1--162:4},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-076-7},
ISSN = {1868-8969},
year = {2018},
volume = {107},
editor = {Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9166},
URN = {urn:nbn:de:0030-drops-91666},
doi = {10.4230/LIPIcs.ICALP.2018.162},
annote = {Keywords: MapReduce, Trees}
}
|
Keywords: |
|
MapReduce, Trees |
|
Collection: |
|
45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
04.07.2018 |
