Link Analysis - Mining of Massive Datasets - page 174

space needed to store the blocks of a stripe at twice the space needed to store the stripe as
a whole.

Figure 5.13 A four-node graph is divided into four 2-by-2 blocks

EXAMPLE 5.8 Let us suppose the matrix from Example 5.7 is partitioned into blocks, with
k = 2. That is, the upper-left quadrant represents links from A or B to A or B , the upper-right
quadrant represents links from C or D to A or B , and so on. It turns out that in this small
example, the only entry that we can avoid is the entry for C in M 22 , because C has no arcs
to either C or D . The tables representing each of the four blocks are shown in Fig. 5.14 .

Figure 5.14 Sparse representation of the blocks of a matrix

If we examine Fig. 5.14(a) , we see the representation of the upper-left quadrant. Notice
that the degrees for A and B are the same as in Fig. 5.11 , because we need to know the entire
number of successors, not the number of successors within the relevant block. However,
each successor of A or B is represented in Fig. 5.14(a) or Fig. 5.14(c) , but not both. Notice
also that in Fig. 5.14(d) , there is no entry for C , because there are no successors of C within
the lower half of the matrix (rows C and D ). □

5.2.5 Other Efficient Approaches to PageRank Iteration

The algorithm discussed in Section 5.2.3 is not the only option. We shall discuss several
other approaches that use fewer processors. These algorithms share with the algorithm of
Section 5.2.3 the good property that the matrix M is read only once, although the vector v