Databases Reference
In-Depth Information
. . .
Figure 5.9: A chain of dead ends
Exercise 5.1.6 : Suppose we recursively eliminate dead ends from the graph,
solve the remaining graph, and estimate the PageRank for the dead-end pages
as described in Section 5.1.4. Suppose the graph is a chain of dead ends, headed
by a node with a self-loop, as suggested in Fig. 5.9. What would be the Page-
Rank assigned to each of the nodes?
Exercise 5.1.7 : Repeat Exercise 5.1.6 for the tree of dead ends suggested by
Fig. 5.10. That is, there is a single node with a self-loop, which is also the root
of a complete binary tree of n levels.
. . .
. . .
. . .
. . .
Figure 5.10: A tree of dead ends
5.2
E
cient Computation of PageRank
To compute the PageRank for a large graph representing the Web, we have
to perform a matrix-vector multiplication on the order of 50 times, until the
vector is close to unchanged at one iteration. To a first approximation, the
map-reduce method given in Section 2.3.1 is suitable. However, we must deal
with two issues:
1. The transition matrix of the Web M is very sparse. Thus, representing
it by all its elements is highly ine
cient. Rather, we want to represent
the matrix by its nonzero elements.
2. We may not be using map-reduce, or for e
ciency reasons we may wish
to use a combiner (see Section 2.2.4) with the Map tasks to reduce the
amount of data that must be passed from Map tasks to Reduce tasks. In
this case, the striping approach discussed in Section 2.3.1 is not su
cient
to avoid heavy use of disk (thrashing).
We discuss the solution to these two problems in this section.
