05988661

a

05988661 Goodrich, Michael T. Sitchinava, Nodari Zhang, Qin Sorting, searching, and simulation in the mapreduce framework. Asano, Takao (ed.) et al., Algorithms and computation. 22nd international symposium, ISAAC 2011, Yokohama, Japan, December 5--8, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-25590-8/pbk). Lecture Notes in Computer Science 7074, 374-383 (2011). 2011 Berlin: Springer EN

doi:10.1007/978-3-642-25591-5_39

Summary: 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.