On the Complexity of Processing Massive, Unordered, Distributed Data

Details On the Complexity of Processing Massive, Unordered, Distributed Data On the Complexity of Processing Massive, Unordered, Distributed Data

2006-11-21

arxiv.org/abs/cs/0611108v2

Computer Science

Computational Complexity

Scientific paper

An existing approach for dealing with massive data sets is to stream over the input in few passes and perform computations with sublinear resources. This method does not work for truly massive data where even making a single pass over the data with a processor is prohibitive. Successful log processing systems in practice such as Google's MapReduce and Apache's Hadoop use multiple machines. They efficiently perform a certain class of highly distributable computations defined by local computations that can be applied in any order to the input. Motivated by the success of these systems, we introduce a simple algorithmic model for massive, unordered, distributed (mud) computation. We initiate the study of understanding its computational complexity. Our main result is a positive one: any unordered function that can be computed by a streaming algorithm can also be computed with a mud algorithm, with comparable space and communication complexity. We extend this result to some useful classes of approximate and randomized streaming algorithms. We also give negative results, using communication complexity arguments to prove that extensions to private randomness, promise problems and indeterminate functions are impossible. We believe that the line of research we introduce in this paper has the potential for tremendous impact. The distributed systems that motivate our work successfully process data at an unprecedented scale, distributed over hundreds or even thousands of machines, and perform hundreds of such analyses each day. The mud model (and its generalizations) inspire a set of complexity-theoretic questions that lie at their heart.

Affiliated with

Also associated with

No associations

Rating

On the Complexity of Processing Massive, Unordered, Distributed Data 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 On the Complexity of Processing Massive, Unordered, Distributed Data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Complexity of Processing Massive, Unordered, Distributed Data will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-338558