[MUSIC]. 
Okay, so let's look at a simple matrix 
multiplication algorithm in map reduce. 
So, before we get there, just to remind 
you how to think about matrix 
multiplication, we've got. 
A matrix with 4 columns and 2 rows 
multiplied by a matrix with 2 columns and 
4 rows and the output is going to have 
the number of rows from the first matrix 
and the number of columns from the second 
matrix. 
So it's 2 by 2 in this case. 
And, again, just to refresh your memory 
here. 
What is this result? 
Well, it's the first row of the first 
relation You know, the dot product with 
the, with the first column of the second 
matrix. 
Right, so it's 1 dot 1 plus 3 dot 4 plus 
4 dot negative 3 Plus negative 2.0 and 
that should equal 1. 
Okay. 
And so on. 
So that's, let's just say row one and 
column one dotted together gives you this 
position. 
Row two. 
And column one gives you this postition, 
and so on. 
All right, so I'm hoping that was 
intensely boring. 
All right, so in MapReduce, how do we 
want to do this This well. 
What we're provided here is two major C's 
representing a sort of a sparse matrix 
format. 
And a sparse matrix format is going to 
look like this. 
So this is row I D, column I D, and the 
value. 
And the reason I call this the sparse 
matrix format is that it would be 
inefficient to represent a very, very 
large matrix this way. 
If you had a value for every position. 
Right, so if you think about just a multi 
dimensional array in memory. 
You don't have to be explicit about the i 
and j coordinates. 
You only have to be, you only have to 
provide the values. 
but if many of those values in that array 
are missing, then in this representation 
I can just ignore them altogether, I just 
don't put them in. 
All right? 
So anytime a value of zero Just remove 
that tuple altogether. 
Okay. 
So we're given two of these sparse 
matrices represent as Tuples. 
You know, sets of tuples. 
And we're going to do the same trick. 
Matrix multiplied is a binary relation. 
And so we need to lump them all together. 
And we need to tag them with the source. 
And then we need to apply this kind of a 
trick. 
In the map phase, for every element ij of 
a emit several things. 
Emit a tuple where the key equals I comma 
K and I'll you what K is in a second. 
And the value is A, oops sorry, value 
equals a i j Now we're going to emit one 
key value pair of this form for every k 
in 1 to N. 
Now what is N? 
Well, N is the number of Columns in b, in 
the right hand matrix. 
Right? 
So A is an L by M matrix and B is an M by 
N matrix. 
So what is this saying? 
This is saying for every column of B, 
emit a tuple with key I to K and value 
the value at IJ. 
Okay. 
Okay so draw this diagram on the next 
line, that, that explains this. 
But what you're going to be doing is 
going to replicate this value to every 
column in, in B. 
Okay. 
And then for B do the same kind of thing. 
You say the key is going to be equal to i 
k. 
And the value is equal to B. 
J,K OK and youre going to omit on of 
these key value pairs for every I. 
The upside down A for all, for all I and 
1 to L. 
Where L is the number of rows in A 
Alright, so you have to replicate the 
values of B to all the corresponding rows 
of A and you have to replicate the values 
of A to all the corresponding columns of 
B. 
Okay. 
And finally for the reduce phase you 
simply, you, you can do the dot product. 
And produce the output. 
So maybe hard to think about, written out 
in notation like that. 
So think about this sort of 
diagramatically. 
The first, the, the i, you know, the, the 
value i, or the value one, one in a needs 
to be sent. 
Actually, let me back up one step. 
First thing to recognize is that there's 
going to be one reducer per output cell. 
In this algorithm, so here we're going to 
have 6 reducers, and if you had really, 
really large matrices which is why we're 
playing this game as to imagine that we 
have you know 10,000 by 10,000 matrices 
sorry matrix with dimension 10,000 by 
10,000, then this sorts makes more sense. 
So, one reducer per cell, in the, in the 
output matrix. 
Okay? 
And think about what data does it need in 
order to compute its answer? 
Well, it needs, for the reducer, 1, 1 in 
the output. 
It needs all the values from row 1 in A. 
And it needs all the values from b one. 
sorry, for, from the first column of b, 
alright? 
All those need to be sent here. 
Now, fine. 
So maybe, maybe I'll write that real 
quick. 
We need row one, from a. 
And we need column one from B right. 
Now let's think about this second 
position. 
Okay, so this is row one. 
Column two, While here we need row one 
from A and column two. 
From B. 
Right? 
So, that's fine. 
But the problem is we don't have data 
represented in terms of rows and columns 
in the input. 
We have every individual cell. 
So, we have to figure out where should 
this value A11 be sent? 
Well, it needs to be sent to everybody 
that might need it. 
Which means it needs to be sent here 
because we see row 1 from A well this 
isn't row 1 from A therefore it needs to 
go here and the second position is also 
involves row 1 from A so this guy needs 
to be sent to 2 places which is what I 
was trying to draw here with these colors 
you get sense no let me draw some more 
arrows here it gets to cluttered which 
I'm sure it will but will try too anyway. 
It needs to be sent to both of those 
locations. 
So, for every column of b, you need to 
just have row, this value b, sent. 
And similarly for, you know, this guy. 
Right? 
So to, to all the reducers that might 
appear in row that need the data for row 
one, you need to send it to all of them. 
And so this is, the reason I'm sort of 
belaboring this is that this is kind of a 
nice trick that MapReduce can do. 
Remember, you can, you can em, you could 
replicate, right? 
You can send a single value out of the 
mapper to many places. 
And when I say send to many places, I 
don't mean literally sort of, you know, 
write it on the wire and send a packet 
across the network. 
What I mean is attach a value to multiple 
keys. 
And then every individual key will go to 
a different place. 
to a different reducer. 
Okay, and through this trick we can sort 
of arrange for matrix multiply to occur. 
And this arguably scales pretty well 
right. 
We've only, we've done some replication 
but that replication is kind of necessary 
and this whole thing can sort of happen 
in, in parallel. 
and then finally each reducer produces a 
sum, Ai times Bj. 
I'm sorry. 
Produces the dot product of a of row A 
and a column B. 
Okay.