Sorting, Searching, and Simulation in the MapReduce Framework

Abstract

In this paper, we study the MapReduce framework from an algorithmic standpoint and demonstrate the usefulness of our approach by designing and analyzing efficient MapReduce algorithms for fundamental sorting, searching, and simulation problems. This study is motivated by a goal of ultimately putting the MapReduce framework on an equal theoretical footing with the well-known PRAM and BSP parallel models, which would benefit both the theory and practice of MapReduce algorithms. We describe efficient MapReduce algorithms for sorting, multi-searching, and simulations of parallel algorithms specified in the BSP and CRCW PRAM models. We also provide some applications of these results to problems in parallel computational geometry for the MapReduce framework, which result in efficient MapReduce algorithms for sorting, 2- and 3-dimensional convex hulls, and fixed-dimensional linear programming. For the case when mappers and reducers have a memory/message-I/O size of $M=\Theta (N^{\epsilon })$, for a small constant $\epsilon >0$, all of our MapReduce algorithms for these applications run in a constant number of rounds.

16 pages

Cited by in corpus (17)

• When Distributed Computation is Communication Expensive
• Simple Round Compression for Parallel Vertex Cover
• Clustering Via Crowdsourcing
• Connected Components at Scale via Local Contractions
• Parallel Batch-dynamic Trees via Change Propagation
• MapReduce Meets Fine-Grained Complexity: MapReduce Algorithms for APSP, Matrix Multiplication, 3-SUM, and Beyond
• Parallel Algorithms for Geometric Graph Problems
• Distributed Weighted Matching via Randomized Composable Coresets
• Tribes Is Hard in the Message Passing Model
• Experimental Evaluation of Multi-Round Matrix Multiplication on MapReduce
• On the Computational Complexity of MapReduce
• Space and Time Efficient Parallel Graph Decomposition, Clustering, and Diameter Approximation
• Sparse Hopsets in Congested Clique
• Parallel Algorithms for Summing Floating-Point Numbers
• Going for Speed: Sublinear Algorithms for Dense r-CSPs
• Communication complexity of approximate maximum matching in the message-passing model
• STAC: Simultaneous Transmitting and Air Computing in Wireless Data Center Networks