1
00:00:00,036 --> 00:00:05,959
[MUSIC]. 

2
00:00:05,959 --> 00:00:10,705
Okay, so let's look at a simple matrix 
multiplication algorithm in map reduce. 

3
00:00:10,705 --> 00:00:14,233
So, before we get there, just to remind 
you how to think about matrix 

4
00:00:14,233 --> 00:00:18,725
multiplication, we've got. 
A matrix with 4 columns and 2 rows 

5
00:00:18,725 --> 00:00:23,065
multiplied by a matrix with 2 columns and 
4 rows and the output is going to have 

6
00:00:23,065 --> 00:00:27,755
the number of rows from the first matrix 
and the number of columns from the second 

7
00:00:27,755 --> 00:00:33,535
matrix. 
So it's 2 by 2 in this case. 

8
00:00:33,535 --> 00:00:38,170
And, again, just to refresh your memory 
here. 

9
00:00:38,170 --> 00:00:44,686
What is this result? 
Well, it's the first row of the first 

10
00:00:44,686 --> 00:00:53,266
relation You know, the dot product with 
the, with the first column of the second 

11
00:00:53,266 --> 00:01:02,750
matrix. 
Right, so it's 1 dot 1 plus 3 dot 4 plus 

12
00:01:02,750 --> 00:01:15,840
4 dot negative 3 Plus negative 2.0 and 
that should equal 1. 

13
00:01:15,840 --> 00:01:16,380
Okay. 
And so on. 

14
00:01:16,380 --> 00:01:21,320
So that's, let's just say row one and 
column one dotted together gives you this 

15
00:01:21,320 --> 00:01:24,028
position. 
Row two. 

16
00:01:24,028 --> 00:01:30,960
And column one gives you this postition, 
and so on. 

17
00:01:30,960 --> 00:01:37,076
All right, so I'm hoping that was 
intensely boring. 

18
00:01:37,076 --> 00:01:41,990
All right, so in MapReduce, how do we 
want to do this This well. 

19
00:01:41,990 --> 00:01:52,352
What we're provided here is two major C's 
representing a sort of a sparse matrix 

20
00:01:52,352 --> 00:02:00,465
format. 
And a sparse matrix format is going to 

21
00:02:00,465 --> 00:02:06,216
look like this. 
So this is row I D, column I D, and the 

22
00:02:06,216 --> 00:02:09,680
value. 
And the reason I call this the sparse 

23
00:02:09,680 --> 00:02:12,748
matrix format is that it would be 
inefficient to represent a very, very 

24
00:02:12,748 --> 00:02:17,510
large matrix this way. 
If you had a value for every position. 

25
00:02:17,510 --> 00:02:22,830
Right, so if you think about just a multi 
dimensional array in memory. 

26
00:02:22,830 --> 00:02:25,510
You don't have to be explicit about the i 
and j coordinates. 

27
00:02:25,510 --> 00:02:28,470
You only have to be, you only have to 
provide the values. 

28
00:02:28,470 --> 00:02:33,570
but if many of those values in that array 
are missing, then in this representation 

29
00:02:33,570 --> 00:02:39,208
I can just ignore them altogether, I just 
don't put them in. 

30
00:02:39,208 --> 00:02:45,003
All right? 
So anytime a value of zero Just remove 

31
00:02:45,003 --> 00:02:50,158
that tuple altogether. 
Okay. 

32
00:02:50,158 --> 00:02:55,502
So we're given two of these sparse 
matrices represent as Tuples. 

33
00:02:55,502 --> 00:02:59,600
You know, sets of tuples. 
And we're going to do the same trick. 

34
00:02:59,600 --> 00:03:03,620
Matrix multiplied is a binary relation. 
And so we need to lump them all together. 

35
00:03:03,620 --> 00:03:09,853
And we need to tag them with the source. 
And then we need to apply this kind of a 

36
00:03:09,853 --> 00:03:14,350
trick. 
In the map phase, for every element ij of 

37
00:03:14,350 --> 00:03:22,245
a emit several things. 
Emit a tuple where the key equals I comma 

38
00:03:22,245 --> 00:03:30,926
K and I'll you what K is in a second. 
And the value is A, oops sorry, value 

39
00:03:30,926 --> 00:03:36,816
equals a i j Now we're going to emit one 
key value pair of this form for every k 

40
00:03:36,816 --> 00:03:42,400
in 1 to N. 
Now what is N? 

41
00:03:42,400 --> 00:03:59,370
Well, N is the number of Columns in b, in 
the right hand matrix. 

42
00:03:59,370 --> 00:04:02,574
Right? 
So A is an L by M matrix and B is an M by 

43
00:04:02,574 --> 00:04:07,461
N matrix. 
So what is this saying? 

44
00:04:07,461 --> 00:04:14,364
This is saying for every column of B, 
emit a tuple with key I to K and value 

45
00:04:14,364 --> 00:04:19,360
the value at IJ. 
Okay. 

46
00:04:19,360 --> 00:04:23,380
Okay so draw this diagram on the next 
line, that, that explains this. 

47
00:04:23,380 --> 00:04:26,796
But what you're going to be doing is 
going to replicate this value to every 

48
00:04:26,796 --> 00:04:29,446
column in, in B. 
Okay. 

49
00:04:29,446 --> 00:04:38,153
And then for B do the same kind of thing. 
You say the key is going to be equal to i 

50
00:04:38,153 --> 00:04:46,496
k. 
And the value is equal to B. 

51
00:04:46,496 --> 00:04:56,320
J,K OK and youre going to omit on of 
these key value pairs for every I. 

52
00:04:56,320 --> 00:05:05,320
The upside down A for all, for all I and 
1 to L. 

53
00:05:05,320 --> 00:05:09,082
Where L is the number of rows in A 
Alright, so you have to replicate the 

54
00:05:09,082 --> 00:05:13,504
values of B to all the corresponding rows 
of A and you have to replicate the values 

55
00:05:13,504 --> 00:05:18,610
of A to all the corresponding columns of 
B. 

56
00:05:18,610 --> 00:05:21,460
Okay. 
And finally for the reduce phase you 

57
00:05:21,460 --> 00:05:28,590
simply, you, you can do the dot product. 
And produce the output. 

58
00:05:28,590 --> 00:05:30,940
So maybe hard to think about, written out 
in notation like that. 

59
00:05:30,940 --> 00:05:34,490
So think about this sort of 
diagramatically. 

60
00:05:34,490 --> 00:05:39,235
The first, the, the i, you know, the, the 
value i, or the value one, one in a needs 

61
00:05:39,235 --> 00:05:43,429
to be sent. 
Actually, let me back up one step. 

62
00:05:43,429 --> 00:05:48,358
First thing to recognize is that there's 
going to be one reducer per output cell. 

63
00:05:48,358 --> 00:05:52,518
In this algorithm, so here we're going to 
have 6 reducers, and if you had really, 

64
00:05:52,518 --> 00:05:56,808
really large matrices which is why we're 
playing this game as to imagine that we 

65
00:05:56,808 --> 00:06:01,228
have you know 10,000 by 10,000 matrices 
sorry matrix with dimension 10,000 by 

66
00:06:01,228 --> 00:06:11,603
10,000, then this sorts makes more sense. 
So, one reducer per cell, in the, in the 

67
00:06:11,603 --> 00:06:15,760
output matrix. 
Okay? 

68
00:06:15,760 --> 00:06:19,810
And think about what data does it need in 
order to compute its answer? 

69
00:06:19,810 --> 00:06:24,750
Well, it needs, for the reducer, 1, 1 in 
the output. 

70
00:06:24,750 --> 00:06:34,188
It needs all the values from row 1 in A. 
And it needs all the values from b one. 

71
00:06:34,188 --> 00:06:38,320
sorry, for, from the first column of b, 
alright? 

72
00:06:38,320 --> 00:06:40,706
All those need to be sent here. 
Now, fine. 

73
00:06:40,706 --> 00:06:48,624
So maybe, maybe I'll write that real 
quick. 

74
00:06:48,624 --> 00:07:01,150
We need row one, from a. 
And we need column one from B right. 

75
00:07:01,150 --> 00:07:06,702
Now let's think about this second 
position. 

76
00:07:06,702 --> 00:07:17,133
Okay, so this is row one. 
Column two, While here we need row one 

77
00:07:17,133 --> 00:07:25,443
from A and column two. 
From B. 

78
00:07:25,443 --> 00:07:27,607
Right? 
So, that's fine. 

79
00:07:27,607 --> 00:07:32,279
But the problem is we don't have data 
represented in terms of rows and columns 

80
00:07:32,279 --> 00:07:36,010
in the input. 
We have every individual cell. 

81
00:07:36,010 --> 00:07:40,790
So, we have to figure out where should 
this value A11 be sent? 

82
00:07:40,790 --> 00:07:45,390
Well, it needs to be sent to everybody 
that might need it. 

83
00:07:45,390 --> 00:07:48,522
Which means it needs to be sent here 
because we see row 1 from A well this 

84
00:07:48,522 --> 00:07:51,978
isn't row 1 from A therefore it needs to 
go here and the second position is also 

85
00:07:51,978 --> 00:07:55,218
involves row 1 from A so this guy needs 
to be sent to 2 places which is what I 

86
00:07:55,218 --> 00:07:58,674
was trying to draw here with these colors 
you get sense no let me draw some more 

87
00:07:58,674 --> 00:08:07,139
arrows here it gets to cluttered which 
I'm sure it will but will try too anyway. 

88
00:08:07,139 --> 00:08:09,745
It needs to be sent to both of those 
locations. 

89
00:08:09,745 --> 00:08:16,460
So, for every column of b, you need to 
just have row, this value b, sent. 

90
00:08:17,560 --> 00:08:19,780
And similarly for, you know, this guy. 
Right? 

91
00:08:19,780 --> 00:08:24,492
So to, to all the reducers that might 
appear in row that need the data for row 

92
00:08:24,492 --> 00:08:30,550
one, you need to send it to all of them. 
And so this is, the reason I'm sort of 

93
00:08:30,550 --> 00:08:33,780
belaboring this is that this is kind of a 
nice trick that MapReduce can do. 

94
00:08:33,780 --> 00:08:36,090
Remember, you can, you can em, you could 
replicate, right? 

95
00:08:36,090 --> 00:08:39,880
You can send a single value out of the 
mapper to many places. 

96
00:08:39,880 --> 00:08:42,856
And when I say send to many places, I 
don't mean literally sort of, you know, 

97
00:08:42,856 --> 00:08:46,500
write it on the wire and send a packet 
across the network. 

98
00:08:46,500 --> 00:08:50,200
What I mean is attach a value to multiple 
keys. 

99
00:08:50,200 --> 00:08:52,250
And then every individual key will go to 
a different place. 

100
00:08:53,560 --> 00:08:57,621
to a different reducer. 
Okay, and through this trick we can sort 

101
00:08:57,621 --> 00:09:02,730
of arrange for matrix multiply to occur. 
And this arguably scales pretty well 

102
00:09:02,730 --> 00:09:05,291
right. 
We've only, we've done some replication 

103
00:09:05,291 --> 00:09:08,842
but that replication is kind of necessary 
and this whole thing can sort of happen 

104
00:09:08,842 --> 00:09:15,407
in, in parallel. 
and then finally each reducer produces a 

105
00:09:15,407 --> 00:09:22,259
sum, Ai times Bj. 
I'm sorry. 

106
00:09:22,259 --> 00:09:28,245
Produces the dot product of a of row A 
and a column B. 

107
00:09:28,245 --> 00:09:31,998
Okay.