Sorting, Searching, and Simulation in the MapReduce Framework
Michael T. Goodrich, Nodari Sitchinava, Qin Zhang · Lecture notes in computer science · 2011
We study the MapReduce framework from an algorithmic standpoint, providing a generalization of the previous algorithmic models for MapReduce. We present optimal solutions for the fundamental problems of all-prefix-sums, sorting and multi-searching. Additionally, we design optimal simulations of the the well-established PRAM and BSP models in MapReduce, immediately resulting in optimal solutions to the problems of computing fixed-dimensional linear programming and 2-D and 3-D convex hulls. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.