Simulating Parallel Algorithms in the MapReduce Framework with Applications to Parallel Computational Geometry

Details Simulating Parallel Algorithms in the MapReduce Framework with Applications to Parallel Computational Geometry Simulating Parallel Algorithms in the MapReduce Framework with Applications to Parallel Computational Geometry

2010-04-27

arxiv.org/abs/1004.4708v1

Computer Science

Data Structures and Algorithms

Version of paper appearing in MASSIVE 2010

Scientific paper

In this paper, we describe efficient MapReduce simulations of parallel algorithms specified in the BSP and PRAM models. We also provide some applications of these simulation results to problems in parallel computational geometry for the MapReduce framework, which result in efficient MapReduce algorithms for sorting, 1-dimensional all nearest-neighbors, 2-dimensional convex hulls, 3-dimensional convex hulls, and fixed-dimensional linear programming. For the case when reducers can have a buffer size of $B=O(n^\epsilon)$, for a small constant $\epsilon>0$, all of our MapReduce algorithms for these applications run in a constant number of rounds and have a linear-sized message complexity, with high probability, while guaranteeing with high probability that all reducer lists are of size $O(B)$.

Affiliated with

Also associated with

No associations

Rating

Simulating Parallel Algorithms in the MapReduce Framework with Applications to Parallel Computational Geometry does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Simulating Parallel Algorithms in the MapReduce Framework with Applications to Parallel Computational Geometry, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Simulating Parallel Algorithms in the MapReduce Framework with Applications to Parallel Computational Geometry will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-236834