1 Map reduce problems
PROBLEMS Join Matrix multiplication 2 / 1 phase Matrix vector multiplication POINTS Map reduce input output Memory requirement Reducer size Communication cost P1 Join: R ( A , B ) S ( A , C ) 1. Map r ( a , b ) => ( a , ( 'R' , b )); s ( a , c ) => ( a , ( 'S' , c )) 2. Reduce ( a , [( 'R' , b ), ( 'S' , c1 ), ( 'S' , c2 )]) => ( a , ( b , c1 )), ( a , ( b , c2 )) Dangling tuples: Key with values from only 1 relation ( a , [( 'R' , b )]) => left dangling ; ( a , [( 'S' , c )]) => right dangling P2 Matrix-multiplication C mXn = A mXp B pXn 2 phase: a. phase1 product Map : Extract key from A ’ s c , B ’ s r A [ i , k ] => ( k , ( 'A' , i , A [ i , k ])) ; B [ k , j ] => ( k , ( 'B' , j , B [ k , j ])) Communication cost : mp + np Reduce...