CODEWITHSUNDEEP
javaalgorithmmathhadoopmapreduce
Daniel
Daniel

Reputation: 27619

Function composition in MapReduce

Let's say we have 2 files f1 and f2 whose key-value pairs represent functions in the mathematical sense. What is the simplest way to find their composition using MapReduce? What is the most efficient way?

For example, given:

f1
a -> b
x -> y
s -> t

f2
b -> c
t -> r

f1 . f2 (composition of f1 and f2) would be
a -> c
s -> r

Upvotes: 1

Views: 110

Answers (1)

rici
rici

Reputation: 241861

  1. Invert f1 to f1'

  2. Map reduce over f1' and f2 simultaneously. For each x->v2 in f2, and for all x->k1 in f1' (if any), output k1->v2.

This will only work if f1 has a reasonably large range. If too many k1 map to the same v1, then the corresponding map worker will be swamped.

Upvotes: 1

Related Questions