0

I am working on map reduce program and was thinking about designing computations of the form where a1, b1 are the values associated with a key

  a1/b1, a1+a2/b1+b2, a1+a2+a3/b1+b2+b3 ...

So at every stage of reducer I would require the previous values. How would one design this as a map reduce as at every stage only the values associated with a particular key can be read.

If you feel the question is not clear, can you guide me towards this general question?

More general question: How would one develop a Fibonacci series using recursion in map reduce?

EDIT

Can you help me with my modified design

 key1, V1,V2,V3
 Key2, V4,V5,V6

Mapper output

  Key1_X V1
  Key1_Y V2
  Key2_X V4
  Key2_Y V5

Reducer output

  Key1_X {V1,.....}
  Key1_Y {V2,.....}

similarly, now in the next mapper stage. Can I create a list like this:

   key1 {V1,....} {V2,....}
   Key2 {V4,....} {V5,....}

My reason to do this, is to perform:

   Key1 {V1/V2, V1+V6/V2+V7, V1+V6+..../V2+V7+.. , .........}

Is it possible to do this? Because the data set is very large, so I think it will be better to use map reduce.

Will changing the design help make it more efficient?

2
  • 1
    Are there invisible parentheses surrounding the terms on either side of the division operator?
    – Atreys
    Jul 15, 2011 at 20:58
  • Changing the wording of your question doesn't change the underlying problem with the problem you are solving. I still think MR is inefficient for this class of problems. Jul 17, 2011 at 21:24

2 Answers 2

7

The main problem with Fibonacci (and as you indicated in your specific problem too) is the dependence between all terms in the series. You cannot calculate the later terms without calculating the earlier terms first.

MapReduce is very good IFF you can split your job into independent pieces.

I don't see an easy way to do this.

So any construct "forcing" MapReduce to solve this will break the scalability advantages. Hence a simple highly optimized loop in your favorite programming language will outperform any MapReduce algorithm.

4
0

Write your mapper/reducer to calculate these three things:

the sum of a_i
the sum of b_i
their ratio

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.