Sunday, September 05, 2010

MapReduce Prefix Sums

Input is a set of items (i, v_i), for 1=1, ..., n, distributed in arbitrary order among m machines with memory M each. Output should be (i, s_i=\sum_{j\leq i} v_j), for all i, again distributed in arbitrary order on the machines. This is the prefix sums problem for massive, unordered, distributed (MUD) data. We need to solve this using MapReduce. I can design an algorithm that will take 3 phases of Map+Reduce with suitable assumptions about n vs M, maybe even 2. Can someone show this can not be done in one phase of Map+Reduce?



Anonymous Anonymous said...

Why don't you post the question on

1:51 PM  
Blogger Mihai said...

Hi Muthu! I guess the model is not 100% clear in my head.

Do you care about the work? How does your algorithm run? Does it do O(n^2) work?

11:45 AM  
Anonymous Hagit said...

Another model clarification question:

Can you do summation, i.e., compute \sum_{i=1,..,n} v_i, in a single map-reduce phase? (If so, how?)

1:42 PM  
Blogger Francesco said...

Each reduce can compute at most M (partial) prefix sums in a round. Then if M<n, you need at least two rounds. In general, at least (\log_M n) rounds?

1:53 PM  
Anonymous Anonymous said...

Dear Mihai, Hagit and Francesco,

Apologies for the late response. Someone (u know who) told me "there is no bigger impediment to scientific progress than the stroller in the hallway."

* What I had in mind was the trivial algorithm. Each machine j works on jn/M + 1 ... (j+1)n/M items and computes required partial prefix sums. Then all prefix sums for the n/M sized problem is computed (I assumed, this will fit into mem of one machine. M like 1000's, internal mem like xGB, n like xTB) and then finally finish up for each piece. So, total "work" is O(n).

* This does not take advantage of fun things Reduce can do. For example, we can assume \sum_{i=1,..,n} v_i can be done in single MR phase. Can other computations be piggybacked on the underlying tree computation?

Part of the problem is to fix some capability for MR.

-- Metoo

3:02 AM  
Blogger Unknown said...

shijun 6.5
michael kors outlet
louis vuitton
louis vuitton
jordan 4 retro
ralph lauren uk
kate spade
coach factorty outlet
michael kors uk
louis vuitton handbags
louis vuitton outlet
adidas shoes
christian louboutin outlet
louis vuitton
ray ban wayfarer
coach outlet
jordan 13s
louis vuitton outlet
pandara jewelry
christian louboutin sale
coach outlet
running warehouse
michael kors
michael kors outlet
ray ban sunglasses
coach outlet
adidas running shoes
louis vuitton
mulberry bags
tods sale
gucci outlet
coach outlet
christian louboutin shoes
louis vuitton outlet
concord 11
cheap jerseys wholesale
copy watches
cheap oakleys
kate spade totes
fitflop outlet
hollister outlet

7:20 PM  
Blogger 750unique said...

oakley sunglasses outlet
coach outlet store online
pandora charms
abercrombie kids
oakley outlet store
nike pas cher
oakley sunglasses sale
ralph lauren polo shirts
oakley sunglasses cheap
coach outlet
tory burch handbags
chanel handbags
cheap ray bans
coach factory outlet
true religion
pandora jewelry outlet
air force pas cher
ray ban glasses
louis vuitton borse
coach outlet
michael kors outlet
mont blanc pens
tory burch outlet online
cheap oakleys
cheap air max
michael kors
soccer outlet
hollister outlet
ed hardy uk
michael kors uk outlet
michael kors outlet online
gucci borse
mcm outlet online

2:57 AM  

Post a Comment

<< Home