[MUSIC]. 
Okay. 
So, let's talk about another example that 
is sort of similar to this very simple 
word count example but, but has a slight 
change. 
Okay, so I want to know/g, maybe the 
makeup of a Corpus of documents instead 
of documents. 
and we're trying to understand the 
characteristics of word length. 
So now instead of a histogram on word 
usage, we're going to group things based 
on the length of the word. 
You know, here we might group words into 
big words, medium, small words, and tiny 
words. 
Where the big words are everything that's 
ten plus letters. 
And the medium words are in red here, and 
they're everything from five to nine 
letters, and so on. 
And you could define your own sort of 
bucketing scheme, or just not even try to 
bucket them and use the exact number, 
okay. 
So, you know, what, what, what we're 
basically showing here, so I'm hoping 
that some of you are, are already kind of 
seeing how this is a, a essentially 
trivial variant of what we already just 
did and this is some, one of the points I 
wanted to make is that you'll see these 
patterns in designing map reduce albums 
come up again and again so I want you to 
get a feel for how to do it. 
It won't be that every new problem looks, 
looks different but the other, the other 
thing I want to talk about, in next few 
slides, I think, is that. 
I-, it shows a little bit more detail in 
how these things are broken up. 
So, for example, if this is a document 
well, here, I guess the point I want to 
make is that before we sort of assume 
that every document was a small but it's 
not impossible that you might have one 
document that's, very very large. 
This typically wouldn't happen with a 
document, and, for, various reasons. 
but imagine these weren't just documents 
but these were, big data sets of, words. 
And so every document itself. 
each an individual document may be so 
large that it can't be processed by a 
single map function at a time. 
And so the question is are we s, are we 
stuck here? 
Is this is the, is the map reduce 
framework broken and is going to crash? 
And the answer is no. 
What will happen is when you. 
Load this large document into the 
system-supporting map reduce. 
And we'll talk a little bit more about 
what that sys, what this lower-level 
system is, wha, what I mean by loading 
the file system underneath map reduce, 
underneath implementations of map reduce. 
When you do that loading, the file, the 
data set, the file, will automatically be 
split into chunks and so we can pretend 
that this document was so large that it 
needed to be split into chunks, okay? 
And so chunk one is this top part and 
chunk two is this small part. 
Now, if the small document is underneath 
the chunk size then it won't get split 
but a large document will. 
Okay. 
And so, this could have happened with the 
word count example, too. 
This is not something specific to word 
link, obviously. 
But it's, it's another twist that we're, 
that we're exploring, okay.. 
So fine. 
So now, this top chunk gets assigned to 
map task 1. 
And it produces, this little histogram, 
of of the counts of yellow words, red 
words, blue words, and. 
Pink words, and we can imagine, you know, 
you should think about how, how the code 
might look if you were to, if you had to 
write this. 
Right, you would need to take the length, 
and you know, iterate over all the words 
in the document just like we did before, 
but now instead of emitting a key being 
the word itself, you would emit, you 
would count its length And put in the 
case statement. 
And figure out what color it is in this, 
in this notation. 
And add that to account. 
Okay, [INAUDIBLE]. 
So the output is these four key value 
pairs. 
And in chunk two, we do the same thing, 
and produce a different set of four key 
value pairs. 
Then in the shuffle step, all the yellow 
key value pairs will be grouped together. 
And there's two of them. 
And all the red ones are grouped together 
and so on. 
And then in the reduce phase, you'll add 
these two numbers together. 
To produce 37. 
Okay. 
So the structure here is really identical 
to word count. 
It's just basically a change to the map 
function. 
And in fact, in this case you can 
actually literally use the exact same 
reduce function. 
Alright, for every key, add up all the 
contributions of it. 
You wouldn't need to change or reduce at 
all. 
And this is something else you'll see, is 
that, you know, certain reduced 
functions, certain functions are more 
general than others, and you'll reuse 
them time and again. 
For example, counting things and adding 
things up is pretty common in these 
map-reduced, in, in these map-reduced 
algorithms, and so reduced. 
General reduce functions that add things 
and count things come up time and again. 
Okay, fine. 
Word count is the economical place to 
start when thinking about map_reduce, 
word length is a very minor variation on 
that. 
So. 
let's think of, of another sort of minor 
variation. 
And this one is arguably even simpler 
than, than word count. 
So, here we want to build an inverted 
index. 
And what an inverted index is, is when 
you have a corpus of documents, you can 
presumably efficiently access any given 
document by it's name. 
Alright, so if you want to look up a url 
on the web. 
You, you can do so. 
But if you, but for a search engine, you 
know very primitive search engine, you 
might want to look up, documents that 
contain a particular word. 
And so building this, index to support 
word look-up to provide documents, is 
called an inverted index, and its one of 
the primitive steps in doing any kind of. 
Text retrieval kind of system. 
Okay. 
So now, you know, imagine we just had 
tweets instead of documents. 
and the input here is that the keys are 
these tweet IDs that I've invented, and 
the value is the text of the tweet 
itself. 
And so the desired output here is the 
word along with a collection of Tweet 
ID's, okay? 
So how do we do this? 
Well, the, the you know, again the code 
is actually simpler than it was Before. 
Because now in the reduced phase, instead 
of, well so we'll, we'll think about it 
for a moment. 
The map phase instead of, instead of 
producing each word, pancake, in one for 
an occurrence. 
We won't do that. 
Instead we'll put out Pancake and the 
document ID itself. 
Right? 
And all of these guys will be produced. 
And so this tweet1, the map, the map task 
that processes this tweet1 will put out 
pancake1, or tweet1. 
Love, tweet1 and so on. 
Okay. 
Further, you know an optimization is, if 
you see the word, I guess I should have 
had an example of this in here, but if 
you see the word pancake twice in the 
same tweet, do you need to put it out, do 
you need to emit the key-value pair 
twice? 
Probably not build this index. 
Because all you're trying to record is of 
the tweet contains the word pancake, not 
that it, not how many times it appears. 
So fine. 
So these key value [INAUDIBLE] get 
shuffled across the network, and now the 
reduce task, what does it do. 
Well, it's going to get a key. 
Pancakes, which should have an s on it, I 
guess. 
And it's going to have an iterator over 
all the document IDs that contain 
pancakes, which in this case is, tweet1 
and tweet. 
2. 
So, do we need to do any processing on 
this key in group of values? 
The answer in this case is no. 
The reduced function is complete is, is 
nonexistent, there's nothing to do, 
alright? 
From what the group is exactly what you 
want in this case. 
And this pattern actually shown, shows 
up. 
Somewhat often as well. 
Where you do want the map and you do want 
the shuffle phase to do the grouping but 
all you wanted to do is to perform the 
grouping, you didn't actually care about 
the reduce function. 
So you're not counting these things, 
you're not adding them up in any way, 
you're not doing and processing on the 
tweets, you just want to omit that. 
And that's perfectly fine because this 
group of values is perfectly serviceable 
as a value itself. 
OK. 
So if you are used to, say, relational 
databases, you know, nested structures 
collections of values within a single 
cell in a table, in a single row, are 
generally disallowed. 
Right, and this is actually first normal 
form, if you're familiar with that. 
but here we don't care. 
If you need, it's, it's. 
For any key in any value, a key can have 
sub structure and a value can have sub 
structure. 
Okay fine so that's how to build an 
inverted index in map produce. 
let me stop there next time we'll talk 
about this relational joint example, so 
this will be how to implement a Join from 
a relational database as a map reduce 
program.