PEGASUS - Large Scale and Big Data: Processing and Management - page 265

1 23456 123456

1
2

1 10000 1

2

100000

1 10000 110001

3
4

0 01100
0 01100

3
4

001110
100100

5
6 00011

0 00011
0

5
6

001011
0 1 0 011

1 2 3 4 5 6 1 4 2 6 3 5

FIGURE 8.3 Clustered vs. nonclustered adjacency matrices for two isomorphic graphs. The
edges are grouped into 2 × 2 blocks. The left graph uses only 3 blocks, whereas the right
graph uses 9 blocks.

8.4.4 GIM-V Di: Di: iagonal b loCk i iteration.
Reducing the number of iterations required for executing an algorithm in MapReduce
mitigates the computational cost a lot, since the main bottleneck of GIM-V is its
shuffling and disk I/O steps. In Hcc, it is possible to decrease the number of itera-
tions when the graph has long chains. The main idea is to multiply diagonal matrix
blocks and corresponding vector blocks as much as possible in one iteration. This is
illustrated in Figure 8.4.

Algorithm 8.3 Renumbering the minimum node

Input: Edge E = {( id src , id dst )},
current minimum vertex id minid cur ,
new minimum vertex id minid new
Output: Renumbered Edge Vidid
src

{ ( ) }

= ′ , ′

dst

1: Renumber-Map(key k , value v ):
2: src ← k ;
3: dst ← v ;
4: if src = minid cur then
5: src ← minid new ;
6: else if src = minid new then
7: src ← minid cur ;
8: end if
9: if dst = minid cur then
10: dst ← minid new ;
11: else if dst = minid new then
12: dst ← minid cur ;
13: end if
14: Output( src , dst );