BIG DATA ANALYTICS
[Link]. - Data Science
Matrix – Multiplication using MapReduce
7 8
1 2 3 58 64
A= B = 9 10 C=
4 5 6 139 154
11 12
Step 1: Represent Matrices as Input Records (Triplets)
Each matrix element is represented as: (matrix name, row, column, value)
Matrix A:
(A,0,0,1) (A,0,1,2) (A,0,2,3)
(A,1,0,4) (A,1,1,5) (A,1,2,6)
Matrix B:
(B,0,0,7) (B,0,1,8)
(B,1,0,9) (B,1,1,10)
(B,2,0,11) (B,2,1,12)
Step 2: Mapper Phase – Emits Key-Value Pairs
Each matrix element is emitted multiple times based on the target output position.
For A[i][k], emit: Key: (i,j) j from 0 to #columns in B Value: (A, k, A[i][k])
For B[k][j], emit: Key: (i,j) i from 0 to #rows in A Value: (B, k, B[k][j])
Example Mapper Output:
A[0][*] = 1, 2, 3 (row 0 of A):
(0,0) → (A,0,1)
(0,0) → (A,1,2)
(0,0) → (A,2,3)
(0,1) → (A,0,1)
(0,1) → (A,1,2)
(0,1) → (A,2,3)
A[1][*] = 4, 5, 6 (row 1 of A):
(1,0) → (A,0,4)
(1,0) → (A,1,5)
(1,0) → (A,2,6)
(1,1) → (A,0,4)
(1,1) → (A,1,5)
(1,1) → (A,2,6)
B[*][0] = 7, 9, 11 (column 0 of B):
(0,0) → (B,0,7)
(0,0) → (B,1,9)
(0,0) → (B,2,11)
(1,0) → (B,0,7)
(1,0) → (B,1,9)
(1,0) → (B,2,11)
B[*][1] = 8, 10, 12 (column 1 of B):
(0,1) → (B,0,8)
(0,1) → (B,1,10)
(0,1) → (B,2,12)
(1,1) → (B,0,8)
(1,1) → (B,1,10)
(1,1) → (B,2,12)
1
Step 3: Shuffle & Sort Phase
Hadoop groups values by key (i, j).
Example for key (0,0): Values: (A,0,1), (A,1,2), (A,2,3), (B,0,7), (B,1,9), (B,2,11)
Step 4: Reducer Phase – Compute Dot Product
For each key (i, j):
1. Match all A[i][k] with B[k][j]
2. Compute sum of A[i][k] × B[k][j]
Key (0,0): 1 × 7 = 7, 2 × 9 = 18, 3 × 11 = 33 Sum: 7 + 18 + 33 = 58
Key (0,1): 1 × 8 = 8, 2 × 10 = 20, 3 × 12 = 36 Sum: 8 + 20 + 36 = 64
Key (1,0): 4 × 7 = 28, 5 × 9 = 45, 6 × 11 = 66 Sum: 28 + 45 + 66 = 139
Key (1,1): 4 × 8 = 32, 5 × 10 = 50, 6 × 12 = 72 Sum: 32 + 50 + 72 = 154
Step 5: Final Output
58 64
C=
139 154
Example – 2
Using MapReduce, perform the multiplication of the following matrices A and B. Clearly
explain the Mapper and Reducer outputs for each stage.
2 4 48 44 26
6 8 5
A = 1 3 B = C = 33 29 17
9 7 4
5 7 93 81 48
Step 1: Dimensions
A: 3 × 2 (3 rows, 2 columns)
B: 2 × 3 (2 rows, 3 columns)
C: 3 × 3
Step 2: Formula
1
X
C[i][j] = A[i][k] × B[k][j]
k=0
Step 3: Mapper Phase – Emits Key-Value Pairs
Matrix A:
Row 0:
(0,0)→(A,0,2)
(0,1)→(A,0,2)
(0,2)→(A,0,2)
(0,0)→(A,1,4)
(0,1)→(A,1,4)
(0,2)→(A,1,4)
Row 1:
(1,0)→(A,0,1)
(1,1)→(A,0,1)
(1,2)→(A,0,1)
(1,0)→(A,1,3)
(1,1)→(A,1,3)
(1,2)→(A,1,3)
Row 2:
(2,0)→(A,0,5)
2
(2,1)→(A,0,5)
(2,2)→(A,0,5)
(2,0)→(A,1,7)
(2,1)→(A,1,7)
(2,2)→(A,1,7)
Matrix B:
Row 0:
(0,0)→(B,0,6)
(1,0)→(B,0,6)
(2,0)→(B,0,6)
(0,1)→(B,0,8)
(1,1)→(B,0,8)
(2,1)→(B,0,8)
(0,2)→(B,0,5)
(1,2)→(B,0,5)
(2,2)→(B,0,5)
Row 1:
(0,0)→(B,1,9)
(1,0)→(B,1,9)
(2,0)→(B,1,9)
(0,1)→(B,1,7)
(1,1)→(B,1,7)
(2,1)→(B,1,7)
(0,2)→(B,1,4)
(1,2)→(B,1,4)
(2,2)→(B,1,4)
Step 4: Reducer Phase – Compute Dot Product
Example: C[0][0]:
From A: (A, 0, 2), (A, 1, 4)
From B: (B, 0, 6), (B, 1, 9)
Sum: 2 × 6 + 4 × 9 = 12 + 36 = 48
C[0][1]: 2 × 8 + 4 × 7 = 16 + 28 = 44
C[0][2]: 2 × 5 + 4 × 4 = 10 + 16 = 26
C[1][0]: 1 × 6 + 3 × 9 = 6 + 27 = 33
C[1][1]: 1 × 8 + 3 × 7 = 8 + 21 = 29
C[1][2]: 1 × 5 + 3 × 4 = 5 + 12 = 17
C[2][0]: 5 × 6 + 7 × 9 = 30 + 63 = 93
C[2][1]: 5 × 8 + 7 × 7 = 40 + 49 = 81
C[2][2]: 5 × 5 + 7 × 4 = 25 + 28 = 48
Step 5: Final Output
48 44 26
C = 33 29 17
93 81 48