Module 4 - MapReduce Theory and Algorithms.ppt

Google puting Faculty Training Workshop
Module IV: MapReduce Theory, Implementation, and Algorithms
This presentation includes content © University of Washington and/or Google, Inc.
Redistributed under the mons Attribution license.
All other contents:
© Spinnaker Labs, Inc.
Overview
Functional Programming Recap
MapReduce Theory & Implementation
MapReduce Algorithms
© Spinnaker Labs, Inc.
Functional Programming Review
Functional operations do not modify data structures: They always create new ones
Original data still exists in unmodified form
Data flows are implicit in program design
Order of operations does not matter
© Spinnaker Labs, Inc.
Functional Programming Review
fun foo(l: int list) =
sum(l) + mul(l) + length(l)
Order of sum() and mul(), etc does not matter – they do not modify l
© Spinnaker Labs, Inc.
Functional Updates Do Not Modify Structures
fun append(x, lst) =
let lst' = reverse lst in
reverse ( x :: lst' )
The append() function above reverses a list, adds a new element to the front, and returns all of that, reversed, which appends an item.
But it never modifies lst!
© Spinnaker Labs, Inc.
Functions Can Be Used As Arguments
fun DoDouble(f, x) = f (f x)
It does not matter what f does to its argument; DoDouble() will do it twice.
What is the type of this function?
© Spinnaker Labs, Inc.
Map
map f lst: (’a->’b) -> (’a list) -> (’b list)
Creates a new list by applying f to each element of the input list; returns output in order.
© Spinnaker Labs, Inc.
Fold
fold f x0 lst: ('a*'b->'b)->'b->('a list)->'b
Moves across a list, applying f to each element plus an accumulator. f returns the next accumulator value, which bined with the next element of the list
© Spinnaker Labs, Inc.
fold left vs. fold right
Order of list elements can be significant
Fold left moves left-to-right across the list
Fold right moves from right-to-left
SML Implementation:
fun foldl f a [] = a
| foldl f a (x::xs) = foldl f (f(x, a)) xs
fun fo