[MUSIC]. 
Last time we talked about scalability, 
and we argued that scalability really 
means working in parallel. 
And we talked about this specific task, 
which is, you know, Read Trimming, okay? 
So this is a bunch of small genetic 
sequences, and your task was to trim off 
the last few characters from each one. 
Okay, and we sort of showed that this is 
pretty simple to think about in parallel. 
You would divide the sets of, the set of 
reads into chunks and put them all onto 
separate computers. 
And process them all in parallel. 
Here, you know there's a function F that 
takes a single read and trims off the 
last few characters and returns the 
prefix. 
and you can apply this function in 
parallel. 
And you can get out, you, the data set 
you want, which is a set of trend reads, 
okay? 
So let's see some more examples. 
So, a new task. 
that was new to be performed at the New 
York Times in 2008. 
And they have a couple blog posts about 
it that you can read was. 
In a simplified version was convert a 
bunch of TIFF images into a different 
format. 
And what was really going on here is that 
they had digitized. 
Images from the newspaper, along with 
some information about the optical 
character recognition, so some extracted 
text. 
And they wanted to turn this into a more 
web, web friendly format. 
And so they had to convert the images to 
a web friendly format and they also had 
to convert the extracted text into a 
little package of JavaScript code. 
Okay? 
So they're getting, get read to put this 
stuff on the web. 
So this is four hundred and five thousand 
images, which was quite a bit, especially 
at the time. 
Okay, but the schematic looks sort of 
similar, right, you take a big set of 
TIFF images and you split them into 
chunks and put them on a bunch of 
different computers. 
and you have a function f that converts a 
TIFF to a PNG, and does the other work 
too, let's say. 
And what you get out is the dataset you 
want, a bunch of PNG images, okay? 
And they're distributed across these, 
these machines. 
Right, so let's look at another example. 
All right, so now we want to run 
thousands of little simulations. 
And what we have are the parameters to 
each one of those thousands of 
simulations. 
And so, and example of this at the URL 
here at the bottom of the slide is from 
simulating muscle dynamics, and this 
comes up a lot, if you have these Monte 
Carlo simulations, they need to do they, 
they understand sort of phenomenon 
stochastically by running lots and lots 
and lots of simulations with different 
kind of, different inputs, and then kind 
of averaging the results. 
Okay. 
As to modeling everything precisely. 
So now you want to run thousands of 
simulations. 
Well, you have a set of inputs, of 
parameters, to these simulations. 
And you break them into chunks and put 
them all in separate machines. 
And apply the function, and here the 
function is actually running the 
simulation. 
And what you get out is the output of the 
stimulation distributed across all the 
machines. 
Okay. 
So there's, you know, a pattern should be 
emerging here, right? 
So another example, so imagine each one 
of these little bars is a document. 
And your task is just to find the most 
common word in every individual document. 
Okay. 
Well, same thing, distribute the 
documents across the k computers. 
And then your function f now in this case 
opens up a single document, figures out 
which word is the most common in that 
document, and then just produces that 
word. 
And so now you have a big distributed 
list of pairs where, you know, the first 
part of the pair is the document ID and 
the second one is the word. 
Okay, so that could be useful but it's a 
bit contrived. 
You know, consider a slightly more 
general program that computes the word 
frequency of every word still in a single 
document. 
Right? 
So instead of just finding the most 
common one and producing that, now you're 
going to produce [INAUDIBLE] histogram of 
the frequencies of every word in the 
document. 
Okay, so given this Input, you produce 
all of these items. 
Right? 
A set of items. 
And the only reason I'm making this 
distinction from the last one is that the 
last one, you know, took a single 
document to produce a single word. 
And now we're taking a single [INAUDIBLE] 
just want to make that clear that that's 
allowed. 
Okay. 
Looks like the animation isn't here, but 
I don't think I'll wind up fixing it. 
So you have millions of documents, you 
distribute them again, now your function 
returns a set of word frequency pairs, 
right? 
But that's okay, and now we have, you 
know, lots of little lines here. 
[NOISE] a single word, let's say. 
So they're not one to one any more. 
But that's no problem the function just 
returns a set of things. 
So there should be a pattern here, right? 
We have a function that maps a read to a 
trimmed read. 
We have a function that maps a TIFF image 
to a PNG image. 
A function that maps a set of parameters 
to the simulation result. 
Alright, it's the simulation itself. 
We have a function that maps a document 
to its most common word. 
And we have a function that maps a 
document to the histogram of its word 
frequencies. 
Okay? 
So, so good. 
So these kinds of tasks we think we know 
how to do in parallel. 
Given a big set of objects and a function 
that knows how to process a single object 
you know, you should be able to think 
about how to paralyze this. 
[INAUDIBLE] but we should abstractly 
understand how this is done. 
Right? 
So, I'll say that one more time. 
We have a big set of objects, we have a 
function Maps a single object [INAUDIBLE] 
computers. 
Okay? 
The objects among the computers and 
function that can parallel. 
This is trivial. 
Alright. 
Okay, so what if we want to compute the 
word frequency across all documents not 
just uh, [INAUDIBLE] frequencies for each 
document [INAUDIBLE] frequencies for a 
single document. 
Okay, so here you know, if we have one of 
these three documents, now we want to get 
a single histogram that counts out the 
number of times the word people appears 
across all three of them, the number 
times the word, government appears across 
all three of them and so on. 
So, let's go back to our schematic here, 
the pattern. 
Well, now we want to compute the word, 
frequency, across five million documents. 
And we can still distribute them among k 
computers, you know. 
So far, so good. 
And then for each document we return a 
set of word frequency pairs and now I've 
switched the notation here from F to map 
since we can consider this a map, that's 
the, the, the terminology I used. 
Okay, but now what do we do? 
So what we can get out here, what we will 
get out here is a set of Frequency but 
that's not what we want a, one big 
histogram. 
And to build this one big histogram we 
have to make sure that a single computer 
has access to every occurrence of some 
particular term, so. 
[SOUND] If the word history appears in 
some document on this machine, and it 
appears, you know, twice in this 
document, and three times, and two, two 
times in documents on that machine, and 
so on, we have to sort of group those all 
up and send them to, to a single place, 
just so we can count them. 
Okay. 
So, let's look at this again. 
So, we distribute the documents across 
these computers. 
We map apply our map function to each 
document in order to, to produce a set of 
word frequency pairs. 
And now we have a big distributed list of 
these words, sets of word frequencies. 
And now we want to get. 
These workers involved in the process. 
And these guys are going to be the ones 
who count the occurrences of a particular 
word. 
Okay, and so imagine all these little 
colored red lines are occurrences of 
words, such that all the red lines are, 
represent a, a single word occurrences of 
a single word, and all the green lines 
represent a different word, and so on. 
On. 
Well so, these guys are going to sent, to 
their respective locations. 
So, such that, this worker is in charge 
of handling all the occurrences of the 
blue word. 
And this worker is in charge of all the 
occurrences of the red work, and so on. 
Okay, so now instead of lines that go, 
you know, from 1 to 1 we have lines that 
go from this 1 computer to a bunch of 
different computers. 
Okay. 
And so on. 
Alright? 
They just sort of shuffle the data, they 
have to spray this data out across the 
network, in order to regroup it. 
Fine, so now that we have the data 
grouped the way we want and partitioned 
the right way, we can apply another 
function which I'll call the reduced 
function which in this case it doesn't 
really assemble it just counts them and 
that allows us to produce our final 
result which is oh, there are 4 green 
words and 4 red words and 3 blue words. 
Words and so on. 
Okay, so, now the schematic looks a 
little different. 
We have sort of a two-step process. 
So, we start with [SOUND] some large set 
of objects distributed over a bunch of 
machines. 
And then we want to apply some function F 
to each one of those objects. 
And that was our First step. 
But then the output of those functions 
are all going to be redistributed across 
the network and grouped. 
To form groups. 
Okay, and then the second step is to 
process each one of those groups. 
So I'll write, instead of f, I'll write 
map here. 
And I'll write reduce here. 
Okay, and so that's exactly what Map 
Reduce does and we'll explain this in 
more detail next time, but the key idea 
here is that the user, the programmer is 
going to write these two functions, a map 
function and a reduce function, which are 
serial and what I mean by serial is there 
not parallel. 
You don't have to worry about how to 
manage, how to program distributed 
cluster within each one of these 
functions. 
You just write a function map that takes 
in an object of some kind and returns 
some other object. 
And I'm not using objects in this sort of 
object-oriented sense, this is sort of in 
the mathematical sense, just sort of any 
input to produce any kind of output. 
Okay, and then the reduced function takes 
a set of objects which I'll note this way 
and returns some of the kind of object 
and actually this can be a set of objects 
as well. 
And in fact this can be a set of objects 
as well. 
So maybe I'll switch colors here. 
This can actually be a set of things and 
this can actually be a set of things. 
So for example we saw a document 
returning a set of word frequency pairs. 
But, you can think of it. 
It's, it's essentially important to 
understand what's going on here, okay. 
So this is, this is, this is a, an 
interesting hypothesis, right? 
That perhaps all distributed algorithms 
can be expressed as sequences of these 
two step operations, right? 
A map fall by reduce, and then maybe more 
map reduce, map reduce, map reduce. 
As, as needed. 
Okay, and we'll talk about that in more 
detail next time.