Scaling Personalized Web Search

Glen Jeh
Stanford University
glenj@db.stanford.edu
Jennifer Widom
Stanford University
widom@db.stanford.edu
ABSTRACT
Recent web search techniques augment traditional text matching
with a global notion of importance based on the linkage struc-
ture of the web, such as in Googles PageRank algorithm. For
more rened searches, this global notion of importance can be spe-
cialized to create personalized views of importancefor example,
importance scores can be biased according to a user-specied set
of initially-interesting pages. Computing and storing all possible
personalized views in advance is impractical, as is computing per-
sonalized views at query time, since the computation of each view
requires an iterative computation over the web graph. We present
new graph-theoretical results, and a new technique based on these
results, that encode personalized views as partial vectors. Partial
vectors are shared across multiple personalized views, and their
computation and storage costs scale well with the number of views.
Our approach enables incremental computation, so that the con-
struction of personalized views from partial vectors is practical at
query time. We present efcient dynamic programming algorithms
for computing partial vectors, an algorithmfor constructing person-
alized views from partial vectors, and experimental results demon-
strating the effectiveness and scalability of our techniques.
Categories and Subject Descriptors
G.2.2 [Discrete Mathematics]: Graph Theory
General Terms
Algorithms
Keywords
web search, PageRank
1. INTRODUCTION AND MOTIVATION
General web search is performed predominantly through text
queries to search engines. Because of the enormous size of the
web, text alone is usually not selective enough to limit the num-
ber of query results to a manageable size. The PageRank algorithm
[11], among others [9], has been proposed (and implemented in
Google [1]) to exploit the linkage structure of the web to compute

This work was supported by the National Science Foundation un-

der grant IIS-9817799. This is an abbreviated version of the full
paper that omits appendices. The full version is available on the
web at http://dbpubs.stanford.edu/pub/2002-12
Copyright is held by the author/owner(s).
WWW2003, May 2024, 2003, Budapest, Hungary.
ACM 1-58113-680-3/03/0005.
global importance scores that can be used to inuence the rank-
ing of search results. To encompass different notions of importance
for different users and queries, the basic PageRank algorithm can
be modied to create personalized views of the web, redening
importance according to user preference. For example, a user may
wish to specify his bookmarks as a set of preferred pages, so that
any query results that are important with respect to his bookmarked
pages would be ranked higher. While experimentation with the use
of personalized PageRank has shown its utility and promise [5, 11],
the size of the web makes its practical realization extremely dif-
cult. To see why, let us review the intuition behind the PageRank
algorithm and its extension for personalization.
The fundamental motivation underlying PageRank is the recur-
sive notion that important pages are those linked-to by many im-
portant pages. A page with only two in-links, for example, may
seem unlikely to be an important page, but it may be important if
the two referencing pages are Yahoo! and Netscape, which them-
selves are important pages because they have numerous in-links.
One way to formalize this recursive notion is to use the random
surfer model introduced in [11]. Imagine that trillions of random
surfers are browsing the web: if at a certain time step a surfer is
looking at page p, at the next time step he looks at a random out-
neighbor of p. As time goes on, the expected percentage of surfers
at each page p converges (under certain conditions) to a limit r(p)
that is independent of the distribution of starting points. Intuitively,
this limit is the PageRank of p, and is taken to be an importance
score for p, since it reects the number of people expected to be
looking at p at any one time.
The PageRank score r(p) reects a democratic importance
that has no preference for any particular pages. In reality, a user
may have a set P of preferred pages (such as his bookmarks) which
he considers more interesting. We can account for preferred pages
in the random surfer model by introducing a teleportation prob-
ability c: at each step, a surfer jumps back to a random page in
P with probability c, and with probability 1 c continues forth
along a hyperlink. The limit distribution of surfers in this model
would favor pages in P, pages linked-to by P, pages linked-to in
turn, etc. We represent this distribution as a personalized PageRank
vector (PPV) personalized on the set P. Informally, a PPV is a per-
sonalized view of the importance of pages on the web. Rankings of
a users text-based query results can be biased according to a PPV
instead of the global importance distribution.
Each PPV is of length n, where n is the number of pages on
the web. Computing a PPV naively using a xed-point iteration
requires multiple scans of the web graph [11], which makes it im-
possible to carry out online in response to a user query. On the
other hand, PPVs for all preference sets, of which there are 2
n
,
is far too large to compute and store ofine. We present a method
271
for encoding PPVs as partially-computed, shared vectors that are
practical to compute and store ofine, and from which PPVs can
be computed quickly at query time.
In our approach we restrict preference sets P to subsets of a set
of hub pages H, selected as those of greater interest for personal-
ization. In practice, we expect H to be a set of pages with high
PageRank (important pages), pages in a human-constructed di-
rectory such as Yahoo! or Open Directory [2], or pages impor-
tant to a particular enterprise or application. The size of H can be
thought of as the available degree of personalization. We present
algorithms that, unlike previous work [5, 11], scale well with the
size of H. Moreover, the same techniques we introduce can yield
approximations on the much broader set of all PPVs, allowing at
least some level of personalization on arbitrary preference sets.
The main contributions of this paper are as follows.
Amethod, based on new graph-theoretical results (listed next),
of encoding PPVs as partial quantities, enabling an ef-
cient, scalable computation that can be divided between pre-
computation time and query time, in a customized fashion
according to available resources and application requirements.
Three main theorems: The Linearity Theorem allows every
PPV to be represented as a linear combination of basis vec-
tors, yielding a natural way to construct PPVs from shared
components. The Hubs Theorem allows basis vectors to be
encoded as partial vectors and a hubs skeleton, enabling ba-
sis vectors themselves to be constructed from common com-
ponents. The Decomposition Theorem establishes a linear
relationship among basis vectors, which is exploited to min-
imize redundant computation.
Several algorithms for computing basis vectors, specializa-
tions of these algorithms for computing partial vectors and
the hubs skeleton, and an algorithm for constructing PPVs
from partial vectors using the hubs skeleton.
Experimental results on real web data demonstrating the ef-
fectiveness and scalability of our techniques.
In Section 2 we introduce the notation used in this paper and for-
malize personalized PageRank mathematically. Section 3 presents
basis vectors, the rst step towards encoding PPVs as shared com-
ponents. The full encoding is presented in Section 4. Section 5 dis-
cusses the computation of partial quantities. Experimental results
are presented in Section 6. Related work is discussed in Section 7.
Section 8 summarizes the contributions of this paper.
Due to space constraints, this paper omits proofs of the theorems
and algorithms presented. These proofs are included as appendices
in the full version of this paper [7].
2. PRELIMINARIES
Let G = (V, E) denote the web graph, where V is the set of all
web pages and E contains a directed edge p, q iff page p links
to page q. For a page p, we denote by I(p) and O(p) the set of
in-neighbors and out-neighbors of p, respectively. Individual in-
neighbors are denoted as Ii(p) (1 i |I(p)|), and individual
out-neighbors are denoted analogously. For convenience, pages are
numbered from 1 to n, and we refer to a page p and its associated
number i interchangeably. For a vector v, v(p) denotes entry p, the
p-th component of v. We always typeset vectors in boldface and
scalars (e.g., v(p)) in normal font. All vectors in this paper are n-
dimensional and have nonnegative entries. They should be thought
of as distributions rather than arrows. The magnitude of a vector v
is dened to be

n
i=1
v(i) and is written |v|. In this paper, vector
magnitudes are always in [0, 1]. In an implemention, a vector may
be represented as a list of its nonzero entries, so another useful
measure is the size of v, the number of nonzero entries in v.
We generalize the preference set P discussed in Section 1 to a
preference vector u, where |u| = 1 and u(p) denotes the amount
of preference for page p. For example, a user who wants to per-
sonalize on his bookmarked pages P uniformly would have a u
where u(p) =
1
|P|
if p P, and u(p) = 0 if p / P. We formal-
ize personalized PageRank scoring using matrix-vector equations.
Let A be the matrix corresponding to the web graph G, where
Aij =
1
|O(j)|
if page j links to page i, and Aij = 0 otherwise.
For simplicity of presentation, we assume that every page has at
least one out-neighbor, as can be enforced by adding self-links to
pages without out-links. The resulting scores can be adjusted to
account for the (minor) effects of this modication, as specied in
the appendices of the full version of this paper [7].
For a given u, the personalized PageRank equation can be writ-
ten as
v = (1 c)Av + cu (1)
where c (0, 1) is the teleportation constant discussed in Sec-
tion 1. Typically c 0.15, and experiments have shown that small
changes in c have little effect in practice [11]. A solution v to
equation (1) is a steady-state distribution of random surfers under
the model discussed in Section 1, where at each step a surfer tele-
ports to page p with probability c u(p), or moves to a random out-
neighbor otherwise [11]. By a theorem of Markov Theory, a solu-
tion v with |v| = 1 always exists and is unique [10].
1
The solution
v is the personalized PageRank vector (PPV) for preference vec-
tor u. If u is the uniform distribution vector u = [1/n, . . . , 1/n],
then the corresponding solution v is the global PageRank vector
[11], which gives no preference to any pages.
For the readers convenience, Table 1 on the next page lists ter-
minology that will be used extensively in the coming sections.
3. BASIS VECTORS
We present the rst step towards encoding PPVs as shared com-
ponents. The motivation behind the encoding is a simple obser-
vation about the linearity
2
of PPVs, formalized by the following
theorem.
THEOREM 1 (LINEARITY). For any preference vectors u1 and
u2, if v1 and v2 are the two corresponding PPVs, then for any
constants 1, 2 0 such that 1 +2 = 1,
1v1 + 2v2 =
(1 c)A(1v1 +2v2) +c(1u1 +2u2) (2)
Informally, the Linearity Theorem says that the solution to a linear
combination of preference vectors u1 and u2 is the same linear
combination of the corresponding PPVs v1 and v2. The proof is
in the full version [7].
Let x1, . . . , xn be the unit vectors in each dimension, so that
for each i, x
i
has value 1 at entry i and 0 everywhere else. Let r
i
be the PPV corresponding to x
i
. Each basis vector r
i
gives the
distribution of random surfers under the model that at each step,
surfers teleport back to page i with probability c. It can be thought
of as representing page is view of the web, where entry j of r
i
is
1
Specically, v corresponds to the steady-state distribution of an
ergodic, aperiodic Markov chain.
2
More precisely, the transformation from personalization vectors u
to their corresponding solution vectors v is linear.
272
Term Description Section
Hub Set H A subset of web pages. 1
Preference Set P Set of pages on which to personalize 1
(restricted in this paper to subsets of H).
Preference Vector u Preference set with weights. 2
Personalized PageRank Vector (PPV) Importance distribution induced by a preference vector. 2
Basis Vector rp (or r
i
) PPV for a preference vector with a single nonzero entry 3
at p (or i).
Hub Vector rp Basis vector for a hub page p H. 3
Partial Vector (rp r
H
p
) Used with the hubs skeleton to construct a hub vector. 4.2
Hubs Skeleton S Used with partial vectors to construct a hub vector. 4.3
Web Skeleton Extension of the hubs skeleton to include pages not in H. 4.4.3
Partial Quantities Partial vectors and the hubs, web skeletons.
Intermediate Results Maintained during iterative computations. 5.2
Table 1: Summary of terms.
js importance in is view. Note that the global PageRank vector is
1
n
(r1 + +rn), the average of every pages view.
An arbitrary personalization vector ucan be written as a weighted
sum of the unit vectors x
i
:
u =
n

i=1
ix
i
(3)
for some constants 1, . . . , n. By the Linearity Theorem,
v =
n

i=1
ir
i
(4)
is the corresponding PPV, expressed as a linear combination of the
basis vectors r
i
.
Recall from Section 1 that preference sets (now preference vec-
tors) are restricted to subsets of a set of hub pages H. If a basis hub
vector (or hereafter hub vector) for each p H were computed and
stored, then any PPV corresponding to a preference set P of size
k (a preference vector with k nonzero entries) can be computed by
adding up the k corresponding hub vectors rp with the appropriate
weights p.
Each hub vector can be computed naively using the xed-point
computation in [11]. However, each xed-point computation is ex-
pensive, requiring multiple scans of the web graph, and the compu-
tation time (as well as storage cost) grows linearly with the number
of hub vectors |H|. In the next section, we enable a more scalable
computation by constructing hub vectors from shared components.
4. DECOMPOSITIONOFBASISVECTORS
In Section 3 we represented PPVs as a linear combination of
|H| hub vectors rp, one for each p H. Any PPV based on
hub pages can be constructed quickly from the set of precomputed
hub vectors, but computing and storing all hub vectors is imprac-
tical. To compute a large number of hub vectors efciently, we
further decompose them into partial vectors and the hubs skeleton,
components from which hub vectors can be constructed quickly at
query time. The representation of hub vectors as partial vectors and
the hubs skeleton saves both computation time and storage due to
sharing of components among hub vectors. Note, however, that de-
pending on available resources and application requirements, hub
vectors can be constructed ofine as well. Thus query time can
be thought of more generally as construction time.
We compute one partial vector for each hub page p, which es-
sentially encodes the part of the hub vector rp unique to p, so that
components shared among hub vectors are not computed and stored
redundantly. The complement to the partial vectors is the hubs
skeleton, which succinctly captures the interrelationships among
hub vectors. It is the blueprint by which partial vectors are as-
sembled to form a hub vector, as we will see in Section 4.3.
The mathematical tools used in the formalization of this decom-
position are presented next.
3
4.1 Inverse P-distance
To formalize the relationship among hub vectors, we relate the
personalized PageRank scores represented by PPVs to inverse P-
distances in the web graph, a concept based on expected-f dis-
tances as introduced in [8].
Let p, q V . We dene the inverse P-distance r

p
(q) from p to
q as
r

p
(q) =

t:pq
P[t]c(1 c)
l(t)
(5)
where the summation is taken over all tours t (paths that may con-
tain cycles) starting at p and ending at q, possibly touching p or q
multiple times. For a tour t = w1, . . . , w
k
, the length l(t) is k
1, the number of edges in t. The term P[t], which should be inter-
preted as the probability of traveling t, is dened as

k1
i=1
1
|O(w
i
)|
,
or 1 if l(t) = 0. If there is no tour from p to q, the summation is
taken to be 0.
4
Note that r

p
(q) measures distances inversely: it is
higher for nodes q closer to p. As suggested by the notation and
proven in the full version [7], r

p
(q) = rp(q) for all p, q V , so
we will use rp(q) to denote both the inverse P-distance and the per-
sonalized PageRank score. Thus PageRank scores can be viewed
as an inverse measure of distance.
Let H V be some nonempty set of pages. For p, q V ,
we dene r
H
p
(q) as a restriction of rp(q) that considers only tours
which pass through some page h H in equation (5). That is, a
page h H must occur on t somewhere other than the endpoints.
3
Note that while the mathematics and computation strategies in this
paper are presented in the specic context of the web graph, they
are general graph-theoretical results that may be applicable in other
scenarios involving stochastic processes, of which PageRank is one
example.
4
The denition here of inverse P-distance differs slightly from the
concept of expected-f distance in [8], where tours are not allowed
to visit q multiple times. Note that general expected-f distances
have the form

t
P[t]f(l(t)); in our denition, f(x) = c(1c)
x
.
273
Precisely, r
H
p
(q) is written as
r
H
p
(q) =

t:pHq
P[t]c(1 c)
l(t)
(6)
where the notation t : p H q reminds us that t passes
through some page in H. Note that t must be of length at least 2.
In this paper, H is always the set of hub pages, and p is usually a
hub page (until we discuss the web skeleton in Section 4.4.3).
4.2 Partial Vectors
Intuitively, r
H
p
(q), dened in equation (6), is the inuence of p
on q through H. In particular, if all paths from p to q pass through
a page in H, then H separates p and q, and r
H
p
(q) = rp(q). For
well-chosen sets H (discussed in Section 4.4.2), it will be true that
rp(q) r
H
p
(q) = 0 for many pages p, q. Our strategy is to take
advantage of this property by breaking rp into two components:
(rp r
H
p
) and r
H
p
, using the equation
rp = (rp r
H
p
) +r
H
p
(7)
We rst precompute and store the partial vector (rp r
H
p
) instead
of the full hub vector rp. Partial vectors are cheaper to compute and
store than full hub vectors, assuming they are represented as a list
of their nonzero entries. Moreover, the size of each partial vector
decreases as |H| increases, making this approach particularly scal-
able. We then add r
H
p
back at query time to compute the full hub
vector. However, computing and storing r
H
p
explicitly could be as
expensive as rp itself. In the next section we show how to encode
r
H
p
so it can be computed and stored efciently.
4.3 Hubs Skeleton
Let us briey review where we are: In Section 3 we represented
PPVs as linear combinations of hub vectors rp, one for each p
H, so that we can construct PPVs quickly at query time if we have
precomputed the hub vectors, a relatively small subset of PPVs. To
encode hub vectors efciently, in Section 4.2 we said that instead of
full hub vectors rp, we rst compute and store only partial vectors
(rp r
H
p
), which intuitively account only for paths that do not
pass through a page of H (i.e., the distribution is blocked by H).
Computing and storing the difference vector r
H
p
efciently is the
topic of this section.
It turns out that the vector r
H
p
can be be expressed in terms of the
partial vectors (r
h
r
H
h
), for h H, as shown by the following
theorem. Recall from Section 3 that x
h
has value 1 at h and 0
everywhere else.
THEOREM 2 (HUBS). For any p V , H V ,
r
H
p
=
1
c

hH
(rp(h) c xp(h))
_
r
h
r
H
h
cx
h
_
(8)
In terms of inverse P-distances (Section 4.1), the Hubs Theorem
says roughly that the distance from page p to any page q V
through H is the distance rp(h) from p to each h H times the
distance r
h
(q) from h to q, correcting for the paths among hubs by
r
H
h
(q). The terms c xp(h) and cx
h
deal with the special cases
when p or q is itself in H. The proof, which is quite involved, is in
the full version [7].
The quantity
_
r
h
r
H
h
_
appearing on the right-hand side of (8)
is exactly the partial vectors discussed in Section 4.2. Suppose we
have computed rp(H) = {(h, rp(h)) | h H} for a hub page
p. Substituting the Hubs Theorem into equation 7, we have the
following Hubs Equation for constructing the hub vector rp from
h
1
2
h
h
3
h
4
2
h
h
1
h
3
h
4
h
5
h
5
Hub Vector
p
p
p
Hubs Skeleton
Partial Vectors
0.03
0.16
0.06
0.003
0.001
0.0002
+
=
Figure 1: Intuitive view of the construction of hub vectors from
partial vectors and the hubs skeleton.
partial vectors:
rp = (rp r
H
p
) +
1
c

hH
(rp(h) c xp(h))
__
r
h
r
H
h
_
cx
h
_
(9)
This equation is central to the construction of hub vectors from
partial vectors.
The set rp(H) has size at most |H|, much smaller than the full
hub vector rp, which can have up to n nonzero entries. Further-
more, the contribution of each entry rp(h) to the sum is no greater
than rp(h) (and usually much smaller), so that small values of
rp(h) can be omitted with minimal loss of precision (Section 6).
The set S = {rp(H) | p H} forms the hubs skeleton, giving the
interrelationships among partial vectors.
An intuitive view of the encoding and construction suggested
by the Hubs Equation (9) is shown in Figure 1. At the top, each
partial vector (r
h
r
H
h
), including (rp r
H
p
), is depicted as a
notched triangle labeled h at the tip. The triangle can be thought
of as representing paths starting at h, although, more accurately, it
represents the distribution of importance scores computed based on
the paths, as discussed in Section 4.1. A notch in the triangle shows
where the computation of a partial vector stopped at another hub
page. At the center, a part rp(H) of the hubs skeleton is depicted
as a tree so the assembly of the hub vector can be visualized. The
hub vector is constructed by logically assembling the partial vectors
using the corresponding weights in the hubs skeleton, as shown at
the bottom.
4.4 Discussion
4.4.1 Summary
In summary, hub vectors are building blocks for PPVs corre-
sponding to preference vectors based on hub pages. Partial vectors,
together with the hubs skeleton, are building blocks for hub vec-
274
tors. Transitively, partial vectors and the hubs skeleton are build-
ing blocks for PPVs: they can be used to construct PPVs without
rst materializing hub vectors as an intermediate step (Section 5.4).
Note that for preference vectors based on multiple hub pages, con-
structing the corresponding PPV from partial vectors directly can
result in signicant savings versus constructing from hub vectors,
since partial vectors are shared across multiple hub vectors.
4.4.2 Choice of H
So far we have made no assumptions about the set of hub pages
H. Not surprisingly, the choice of hub pages can have a signif-
icant impact on performance, depending on the location of hub
pages within the overall graph structure. In particular, the size of
partial vectors is smaller when pages in H have higher PageRank,
since high-PageRank pages are on average close to other pages in
terms of inverse P-distance (Section 4.1), and the size of the par-
tial vectors is related to the inverse P-distance between hub pages
and other pages according to the Hubs Theorem. Our intuition is
that high-PageRank pages are generally more interesting for per-
sonalization anyway, but in cases where the intended hub pages
do not have high PageRank, it may be benecial to include some
high-PageRank pages in H to improve performance. We ran exper-
iments conrming that the size of partial vectors is much smaller
using high-PageRank pages as hubs than using random pages.
4.4.3 Web Skeleton
The techniques used in the construction of hub vectors can be
extended to enable at least approximate personalization on arbitrary
preference vectors that are not necessarily based on H. Suppose
we want to personalize on a page p / H. The Hubs Equation
can be used to construct r
H
p
from partial vectors, given that we
have computed rp(H). As discussed in Section 4.3, the cost of
computing and storing rp(H) is orders of magnitude less than rp.
Though r
H
p
is only an approximation to rp, it may still capture
signicant personalization information for a properly-chosen hub
set H, as r
H
p
can be thought of as a projection of rp onto H.
For example, if H contains pages from Open Directory, r
H
p
can
capture information about the broad topic of rp. Exploring the
utility of the web skeleton W = {rp(H) | p V } is an area of
future work.
5. COMPUTATION
In Section 4 we presented a way to construct hub vectors from
partial vectors (rp r
H
p
), for p H, and the hubs skeleton
S = {rp(H) | p H}. We also discussed the web skeleton W =
{rp(H) | p V }. Computing these partial quantities naively us-
ing a xed-point iteration [11] for each p would scale poorly with
the number of hub pages. Here we present scalable algorithms that
compute these quantities efciently by using dynamic program-
ming to leverage the interrelationships among them. We also show
how PPVs can be constructed from partial vectors and the hubs
skeleton at query time. All of our algorithms have the property that
they can be stopped at any time (e.g., when resources are depleted),
so that the current best results can be used as an approximation,
or the computation can be resumed later for increased precision if
resources permit.
We begin in Section 5.1 by presenting a theorem underlying all
of the algorithms presented (as well as the connection between
PageRank and inverse P-distance, as shown in the full version [7]).
In Section 5.2, we present three algorithms, based on this theorem,
for computing general basis vectors. The algorithms in Section 5.2
are not meant to be deployed, but are used as foundations for the
algorithms in Section 5.3 for computing partial quantities. Section
5.4 discusses the construction of PPVs from partial vectors and the
hubs skeleton.
5.1 Decomposition Theorem
Recall the random surfer model of Section 1, instantiated for
preference vector u = xp (for page ps view of the web). At
each step, a surfer s teleports to page p with some probability c. If
s is at p, then at the next step, s with probability 1 c will be at a
random out-neighbor of p. That is, a fraction (1 c)
1
|O(p)|
of the
time, surfer s will be at any given out-neighbor of p one step after
teleporting to p. This behavior is strikingly similar to the model
instantiated for preference vector u

=
1
|O(p)|

|O(p)|
i=1
x
O
i
(p)
,
where surfers teleport directly to each Oi(p) with equal probability
1
|O(p)|
. The similarity is formalized by the following theorem.
THEOREM 3 (DECOMPOSITION). For any p V ,
rp =
(1 c)
|O(p)|
|O(p)|

i=1
r
O
i
(p)
+ cxp (10)
The Decomposition Theorem says that the basis vector rp for p is
an average of the basis vectors r
O
i
(p)
for its out-neighbors, plus a
compensation factor cxp. The proof is in the full version [7].
The Decomposition Theorem gives another way to think about
PPVs. It says that ps view of the web (rp) is the average of the
views of its out-neighbors, but with extra importance given to p
itself. That is, pages important in ps view are either p itself, or
pages important in the view of ps out-neighbors, which are them-
selves endorsed by p. In fact, this recursive intuition yields an
equivalent way of formalizing personalized PageRank scoring: ba-
sis vectors can be dened as vectors satisfying the Decomposition
Theorem.
While the Decomposition Theoremidenties relationships among
basis vectors, a division of the computation of a basis vector rp
into related subproblems for dynamic programming is not inherent
in the relationships. For example, it is possible to compute some
basis vectors rst and then to compute the rest using the former as
solved subproblems. However, the presence of cycles in the graph
makes this approach ineffective. Instead, our approach is to con-
sider as a subproblem the computation of a vector to less precision.
For example, having computed r
O
i
(p)
to a certain precision, we
can use the Decomposition Theorem to combine the r
O
i
(p)
s to
compute rp to greater precision. This approach has the advantage
that precision needs not be xed in advance: the process can be
stopped at any time for the current best answer.
5.2 Algorithms for Computing Basis Vectors
We present three algorithms in the general context of computing
full basis vectors. These algorithms are presented primarily to de-
velop our algorithms for computing partial quantities, presented in
Section 5.3. All three algorithms are iterative xed-point compu-
tations that maintain a set of intermediate results (D
k
[], E
k
[]).
For each p, D
k
[p] is a lower-approximation of rp on iteration k,
i.e., D
k
[p](q) rp(q) for all q V . We build solutions D
k
[p]
(k = 0, 1, 2, . . . ) that are successively better approximations to rp,
and simultaneously compute the error components E
k
[p], where
E
k
[p] is the projection of the vector (rp D
k
[p]) onto the (ac-
tual) basis vectors. That is, we maintain the invariant that for all
k 0 and all p V ,
D
k
[p] +

qV
E
k
[p](q)rq = rp (11)
275
Thus, D
k
[p] is a lower-approximation of rp with error

qV
E
k
[p](q)rq

= |E
k
[p]|
We begin with D0[p] = 0 and E0[p] = xp, so that logically, the
approximation is initially 0 and the error is rp. To store E
k
[p] and
D
k
[p] efciently, we can represent them in an implementation as
a list of their nonzero entries. While all three algorithms have in
common the use of these intermediate results, they differ in how
they use the Decomposition Theorem to rene intermediate results
on successive iterations.
It is important to note that the algorithms presented in this section
and their derivatives in Section 5.3 compute vectors to arbitrary
precision; they are not approximations. In practice, the precision
desired may vary depending on the application. Our focus is on
algorithms that are efcient and scalable with the number of hub
vectors, regardless of the precision to which vectors are computed.
5.2.1 Basic Dynamic Programming Algorithm
In the basic dynamic programming algorithm, a new basis vector
for each page p is computed on each iteration using the vectors
computed for ps out-neighbors on the previous iteration, via the
Decomposition Theorem. On iteration k, we derive (D
k+1
[p],
E
k+1
[p]) from (D
k
[p], E
k
[p]) using the equations:
D
k+1
[p] =
1 c
|O(a)|
|O(p)|

i=1
D
k
[O
i
(p)] + cxp (12)
E
k+1
[p] =
1 c
|O(a)|
|O(p)|

i=1
E
k
[O
i
(p)] (13)
A proof of the algorithms correctness is given in the full version
[7], where the error |E
k
[p]| is shown to be reduced by a factor of
1 c on each iteration.
Note that although the E
k
[] values help us to see the correct-
ness of the algorithm, they are not used here in the computation
of D
k
[] and can be omitted in an implementation (although they
will be used to compute partial quantities in Section 5.3). The sizes
of D
k
[p] and E
k
[p] grow with the number of iterations, and in the
limit they can be up to the size of rp, which is the number of pages
reachable from p. Intermediate scores (D
k
[], E
k
[]) will likely
be much larger than available main memory, and in an implemen-
tation (D
k
[], E
k
[]) could be read off disk and (D
k+1
[],
E
k+1
[]) written to disk on each iteration. When the data for one
iteration has been computed, data from the previous iteration may
be deleted. Specic details of our implementation are discussed in
Section 6.
5.2.2 Selective Expansion Algorithm
The selective expansion algorithm is essentially a version of the
naive algorithm that can readily be modied to compute partial vec-
tors, as we will see in Section 5.3.1.
We derive (D
k+1
[p], E
k+1
[p]) by distributing the error at
each page q (that is, E
k
[p](q)) to its out-neighbors via the Decom-
position Theorem. Precisely, we compute results on iteration-k us-
ing the equations:
D
k+1
[p] = D
k
[p] +

qQ
k
(p)
c E
k
[p](q)xq (14)
E
k+1
[p] = E
k
[p]

qQ
k
(p)
E
k
[p](q)xq+

qQ
k
(p)
1 c
|O(q)|
|O(q)|

i=1
E
k
[p](q)x
O
i
(q)
(15)
for a subset Q
k
(p) V . If Q
k
(p) = V for all k, then the error
is reduced by a factor of 1 c on each iteration, as in the basic
dynamic programming algorithm. However, it is often useful to
choose a selected subset of V as Q
k
(p). For example, if Q
k
(p)
contains the mpages q for which the error E
k
[p](q) is highest, then
this top-m scheme limits the number of expansions and delays the
growth in size of the intermediate results while still reducing much
of the error. In Section 5.3.1, we will compute the hub vectors by
choosing Q
k
(p) = H. The correctness of selective expansion is
proven in the full version [7].
5.2.3 Repeated Squaring Algorithm
The repeated squaring algorithm is similar to the selective ex-
pansion algorithm, except that instead of extending (D
k+1
[],
E
k+1
[]) one step using equations (14) and (15), we compute
what are essentially iteration-2k results using the equations
D
2k
[p] = D
k
[p] +

qQ
k
(p)
E
k
[p](q)D
k
[q] (16)
E
2k
[p] = E
k
[p]

qQ
k
(p)
E
k
[p](q)xq+

qQ
k
(p)
E
k
[p](q)E
k
[q]
(17)
where Q
k
(p) V . For now we can assume that Q
k
(p) = V for
all p; we will set Q
k
(p) = H to compute the hubs skeleton in Sec-
tion 5.3.2. The correctness of these equations is proven in the full
version [7], where it is shown that repeated squaring reduces the
error much faster than the basic dynamic programming or selective
expansion algorithms. If Q
k
(p) = V , the error is squared on each
iteration, as equation (17) reduces to:
E
2k
[p] =

qV
E
k
[p](q)E
k
[q] (18)
As an alternative to taking Q
k
(p) = V , we can also use the top-m
scheme of Section 5.2.2.
Note that while all three algorithms presented can be used to
compute the set of all basis vectors, they differ in their require-
ments on the computation of other vectors when computing rp: the
basic dynamic programming algorithm requires the vectors of out-
neighbors of p to be computed as well, repeated squaring requires
results (D
k
[q], E
k
[q]) to be computed for q such that E
k
[p](q) >
0, and selective expansion computes rp independently.
5.3 Computing Partial Quantities
In Section 5.2 we presented iterative algorithms for computing
full basis vectors to arbitrary precision. Here we present modica-
tions to these algorithms to compute the partial quantities:
Partial vectors (rp r
H
p
), p H.
The hubs skeleton S = {rp(H) | p H} (which can be com-
puted more efciently by itself than as part of the entire web
skeleton).
276
The web skeleton W = {rp(H) | p V }.
Each partial quantity can be computed in time no greater than its
size, which is far less than the size of the hub vectors.
5.3.1 Partial Vectors
Partial vectors can be computed using a simple specialization of
the selective expansion algorithm(Section 5.2.2): we take Q0(p) =
V and Q
k
(p) = V H for k > 0, for all p V . That is, we never
expand hub pages after the rst step, so tours passing through
a hub page H are never considered. Under this choice of Q
k
(p),
D
k
[p]+cE
k
[p] converges to (rp r
H
p
) for all p V . Of course,
only the intermediate results (D
k
[p], E
k
[p]) for p H should be
computed. A proof is presented in the full version [7].
This algorithm makes it clear why using high-PageRank pages
as hub pages improves performance: from a page p we expect to
reach a high-PageRank page q sooner than a random page, so the
expansion from p will stop sooner and result in a shorter partial
vector.
5.3.2 Hubs Skeleton
While the hubs skeleton is a subset of the complete web skeleton
and can be computed as such using the technique to be presented
in Section 5.3.3, it can be computed much faster by itself if we are
not interested in the entire web skeleton, or if higher precision is
desired for the hubs skeleton than can be computed for the entire
web skeleton.
We use a specialization of the repeated squaring algorithm (Sec-
tion 5.2.3) to compute the hubs skeleton, using the intermediate
results from the computation of partial vectors. Suppose (D
k
[p],
E
k
[p]), for k 1, have been computed by the algorithm of Sec-
tion 5.3.1, so that

q / H
E
k
[p](q) < , for some error . We apply
the repeated squaring algorithm on these results using Q
k
(p) = H
for all successive iterations. As shown in the full version [7], after
i iterations of repeated squaring, the total error |E
i
[p]| is bounded
by (1 c)
2
i
+ /c. Thus, by varying k and i, rp(H) can be com-
puted to arbitrary precision.
Notice that only the intermediate results (D
k
[h], E
k
[h]) for
h H are ever needed to update scores for D
k
[p], and of the for-
mer, only the entries D
k
[h](q), E
k
[h](q), for q H, are used to
compute D
k
[p](q). Since we are only interested in the hub scores
D
k
[p](q), we can simply drop all non-hub entries from the inter-
mediate results. The running time and storage would then depend
only on the size of rp(H) and not on the length of the entire hub
vectors rp. If the restricted intermediate results t in main mem-
ory, it is possible to defer the computation of the hubs skeleton to
query time.
5.3.3 Web Skeleton
To compute the entire web skeleton, we modify the basic dy-
namic programming algorithm (Section 5.2.1) to compute only the
hub scores rp(H), with corresponding savings in time and memory
usage. We restrict the computation by eliminating entries q / H
from the intermediate results (D
k
[p], E
k
[p]), similar to the tech-
nique used in computing the hubs skeleton.
The justication for this modication is that the hub score
D
k+1
[p](h) is affected only by the hub scores D
k
[](h) of the pre-
vious iteration, so that D
k+1
[p](h) in the modied algorithm is
equal to that in the basic algorithm. Since |H| is likely to be or-
ders of magnitude less than n, the size of the intermediate results is
reduced signicantly.
5.4 Construction of PPVs
Finally, let us see how a PPV for preference vector u can be
constructed directly from partial vectors and the hubs skeleton us-
ing the Hubs Equation. (Construction of a single hub vector is a
specialization of the algorithm outlined here.) Let u = 1p1 +
+ zpz be a preference vector, where pi H for 1 i z.
Let Q H, and let
ru(h) =
z

i=1
i (rp
i
(h) c xp
i
(h)) (19)
which can be computed from the hubs skeleton. Then the PPV v
for u can be constructed as
v =
z

i=1
i(rp
i
r
H
p
i
)+
1
c

hQ
ru(h)>0
ru(h)
_
(r
h
r
H
h
) cx
h
_
(20)
Both the terms (rp
i
r
H
p
i
) and (r
h
r
H
h
) are partial vectors,
which we assume have been precomputed. The term cx
h
repre-
sents a simple subtraction from (r
h
r
H
h
). If Q = H, then (20)
represents a full construction of v. However, for some applications,
it may sufce to use only parts of the hubs skeleton to compute v
to less precision. For example, we can take Q to be the m hubs h
for which ru(h) is highest. Experimentation with this scheme is
discussed in Section 6.3. Alternatively, the result can be improved
incrementally (e.g., as time permits) by using a small subset Qeach
time and accumulating the results.
6. EXPERIMENTS
We performed experiments using real web data from Stanfords
WebBase [6], a crawl of the web containing 120 million pages.
Since the iterative computation of PageRank is unaffected by leaf
pages (i.e., those with no out-neighbors), they can be removed from
the graph and added back in after the computation [11]. After re-
moving leaf pages, the graph consisted of 80 million pages
Both the web graph and the intermediate results (D
k
[], E
k
[])
were too large to t in main memory, and a partitioning strategy,
based on that presented in [4], was used to divide the computation
into portions that can be carried out in memory. Specically, the set
of pages V was partitioned into k arbitrary sets P1, . . . , P
k
of equal
size (k = 10 in our experiments). The web graph, represented
as an edge-list E, is partitioned into k chunks Ei (1 i k),
where Ei contains all edges p, q for which p Pi. Intermedi-
ate results D
k
[p] and E
k
[p] were represented together as a list
L
k
[p] = (q1, d1, e1), (q2, d2, e2), . . . where D
k
[p](qz) = dz
and E
k
[p](qz) = ez, for z = 1, 2, . . . . Only pages qz for which
either dz > 0 or ez > 0 were included. The set of intermedi-
ate results L
k
[] was partitioned into k
2
chunks L
i,j
k
[], so that
L
i,j
k
[p] contains triples (qz, dz, ez) of L
k
[p] for which p Pi and
qz Pj. In each of the algorithms for computing partial quantities,
only a single column L
,j
k
[] was kept in memory at any one time,
and part of the next-iteration results L
k+1
[] were computed by
successively reading in individual blocks of the graph or interme-
diate results as appropriate. Each iteration requires only one linear
scan of the intermediate results and web graph, except for repeated
squaring, which does not use the web graph explicitly.
6.1 Computing Partial Vectors
For comparison, we computed both (full) hub vectors and partial
vectors for various sizes of H, using the selective expansion al-
277
0
20000
40000
60000
80000
100000
120000
1000 2000 5000 10000 20000 50000 100000
Number of Hubs (log scale)
A
v
e
r
a
g
e

V
e
c
t
o
r

S
i
z
e
Partial Vectors Full Hub Vectors
Figure 2: Average Vector Size vs. Number of Hubs
gorithm with Q
k
(p) = V (full hub vectors) and Q
k
(p) = V H
(partial vectors). As discussed in Section 4.4.2, we found the partial
vectors approach to be much more effective when H contains high-
PageRank pages rather than random pages. In our experiments H
ranged from the top 1000 to top 100, 000 pages with the highest
PageRank. The constant c was set to 0.15.
To evaluate the performance and scalability of our strategy in-
dependently of implementation and platform, we focus on the size
of the results rather than computation time, which is linear in the
size of the results. Because of the number of trials we had to per-
form and limitations on resources, we computed results only up
to 6 iterations, for |H| up to 100, 000. Figure 2 plots the average
size of (full) hub vectors and partial vectors (recall that size is the
number of nonzero entries), as computed after 6 iterations of the se-
lective expansion algorithm, which for computing full hub vectors
is equivalent to the basic dynamic programming algorithm. Note
that the x-axis plots |H| in logarithmic scale.
Experiments were run using a 1.4 gigahertz CPU on a machine
with 3.5 gigabytes of memory. For |H| = 50, 000, the computa-
tion of full hub vectors took about 2.8 seconds per vector, and about
0.33 seconds for each partial vector. We were unable to compute
full hub vectors for |H| = 100, 000 due to the time required, al-
though the average vector size is expected not to vary signicantly
with |H| for full hub vectors. In Figure 2 we see that the reduction
in size from using our technique becomes more signicant as |H|
increases, suggesting that our technique scales well with |H|.
6.2 Computing the Hubs Skeleton
We computed the hubs skeleton for |H| = 10, 000 by running
the selective expansion algorithm for 6 iterations using Q
k
(p) =
H, and then running the repeated squaring algorithm for 10 itera-
tions (Section 5.3.2), where Q
k
(p) is chosen to be the top 50 en-
tries under the top-m scheme (Section 5.2.2). The average size of
the hubs skeleton is 9021 entries. Each iteration of the repeated
squaring algorithm took about an hour, a cost that depends only on
|H| and is constant with respect to the precision to which the partial
0
5000000
10000000
15000000
20000000
25000000
30000000
35000000
40000000
45000000
100 200 500 1000 2000 5000 10000
m (log scale)
A
v
e
r
a
g
e

C
o
n
s
t
r
u
c
t
e
d

V
e
c
t
o
r

S
i
z
e
0
10
20
30
40
50
60
70
A
v
e
r
a
g
e

C
o
n
s
t
r
u
c
t
i
o
n

T
i
m
e

(
s
e
c
o
n
d
s
)
Constructed Vector Size Construction Time
Figure 3: Construction Time and Size vs. Hubs Skeleton Por-
tion (m)
vectors are computed.
6.3 Constructing Hub Vectors from Partial
Vectors
Next we measured the construction of (full) hub vectors from
partial vectors and the hubs skeleton. Note that in practice we may
construct PPVs directly from partial vectors, as discussed in Sec-
tion 5.4. However, performance of the construction would depend
heavily on the users preference vector. We consider hub vector
computation because it better measures the performance benets
of our partial vectors approach.
As suggested in Section 4.3, the precision of the hub vectors con-
structed from partial vectors can be varied at query time according
to application and performance demands. That is, instead of using
the entire set rp(H) in the construction of rp, we can use only the
highest m entries, for m |H|. Figure 3 plots the average size
and time required to construct a full hub vector from partial vec-
tors in memory versus m, for |H| = 10, 000. Results are averaged
over 50 randomly-chosen hub vectors. Note that the x-axis is in
logarithmic scale.
Recall from Section 6.1 that the partial vectors from which the
hubs vector is constructed were computed using 6 iterations, lim-
iting the precision. Thus, the error values in Figure 3 are roughly
16% (ranging from 0.166 for m = 100 to 0.163 for m = 10, 000).
Nonetheless, this error is much smaller than that of the iteration-6
full hub vectors computed in Section 6.1, which have error (1
c)
6
= 38%. Note, however, that the size of a vector is a better in-
dicator of precision than the magnitude, since we are usually most
interested in the number of pages with nonzero entries in the dis-
tribution vector. An iteration-6 full hub vector (from Section 6.1)
for page p contains nonzero entries for pages at most 6 links away
from p, 93, 993 pages on average. In contrast, from Figure 3 we
see that a hub vector containing 14 million nonzero entries can be
constructed from partial vectors in 6 seconds.
278
7. RELATED WORK
The use of personalized PageRank to enable personalized web
search was rst proposed in [11], where it was suggested as a mod-
ication of the global PageRank algorithm, which computes a uni-
versal notion of importance. The computation of (personalized)
PageRank scores was not addressed beyond the naive algorithm.
In [5], personalized PageRank scores were used to enable topic-
sensitive web search. Specically, precomputed hub vectors cor-
responding to broad categories in Open Directory were used to bias
importance scores, where the vectors and weights were selected ac-
cording to the text query. Experiments in [5] concluded that the
use of personalized PageRank scores can improve web search, but
the number of hub vectors used was limited to 16 due to the com-
putational requirements, which were not addressed in that work.
Scaling the number of hub pages beyond 16 for ner-grained per-
sonalization is a direct application of our work.
Another technique for computing web-page importance, HITS,
was presented in [9]. In HITS, an iterative computation similar in
spirit to PageRank is applied at query time on a subgraph consisting
of pages matching a text query and those nearby. Personalizing
based on user-specied web pages (and their linkage structure in
the web graph) is not addressed by HITS. Moreover, the number
of pages in the subgraphs used by HITS (order of thousands) is
much smaller than that we consider in this paper (order of millions),
and the computation from scratch at query time makes the HITS
approach difcult to scale.
Another algorithm that uses query-dependent importance scores
to improve upon a global version of importance was presented in
[12]. Like HITS, it rst restricts the computation to a subgraph de-
rived from text matching. (Personalizing based on user-specied
web pages is not addressed.) Unlike HITS, [12] suggested that
importance scores be precomputed ofine for every possible text
query, but the enormous number of possibilities makes this ap-
proach difcult to scale.
The concept of using hub nodes in a graph to enable partial
computation of solutions to the shortest-path problem was used in
[3] in the context of database search. That work deals with searches
within databases, and on a scale far smaller than that of the web.
Some system aspects of (global) PageRank computation were
addressed in [4]. The disk-based data-partitioning strategy used in
the implementation of our algorithm is adopted from that presented
therein.
Finally, the concept of inverse P-distance used in this paper is
based on the concept of expected-f distance introduced in [8], where
it was presented as an intuitive model for a similarity measure in
graph structures.
8. SUMMARY
We have addressed the problemof scaling personalized web search:
We started by identifying a linear relationship that allows
personalized PageRank vectors to be expressed as a linear
combination of basis vectors. Personalized vectors corre-
sponding to arbitrary preference sets drawn from a hub set
H can be constructed quickly from the set of precomputed
basis hub vectors, one for each hub h H.
We laid the mathematical foundations for constructing hub
vectors efciently by relating personalized PageRank scores
to inverse P-distances, an intuitive notion of distance in ar-
bitrary directed graphs. We used this notion of distance to
identify interrelationships among basis vectors.
We presented a method of encoding hub vectors as partial
vectors and the hubs skeleton. Redundancy is minimized un-
der this representation: each partial vector for a hub page p
represents the part of ps hub vector unique to itself, while
the skeleton species how partial vectors are assembled into
full vectors.
We presented algorithms for computing basis vectors, and
showed how they can be modied to compute partial vectors
and the hubs skeleton efciently.
We ran experiments on real web data showing the effective-
ness of our approach. Results showed that our strategy re-
sults in signicant resource reduction over full vectors, and
scales well with |H|, the degree of personalization.
9. ACKNOWLEDGMENT
The authors thank Taher Haveliwala for many useful discussions
and extensive help with implementation.
10. REFERENCES
[1] http://www.google.com.
[2] http://dmoz.org.
[3] R. Goldman, N. Shivakumar, S. Venkatasubramanian, and
H. Garcia-Molina. Proximity search in databases. In
Proceedings of the Twenty-Fourth International Conference
on Very Large Databases, New York, New York, Aug. 1998.
[4] T. H. Haveliwala. Efcient computation of PageRank.
Technical report, Stanford University Database Group, 1999.
http://dbpubs.stanford.edu/pub/1999-31.
[5] T. H. Haveliwala. Topic-sensitive PageRank. In Proceedings
of the Eleventh International World Wide Web Conference,
Honolulu, Hawaii, May 2002.
[6] J. Hirai, S. Raghavan, A. Paepcke, and H. Garcia-Molina.
WebBase: A repository of web pages. In Proceedings of the
Ninth International World Wide Web Conference,
Amsterdam, Netherlands, May 2000.
http://www-diglib.stanford.edu/testbed/
doc2/WebBase/.
[7] G. Jeh and J. Widom. Scaling personalized web search.
Technical report, Stanford University Database Group, 2002.
http://dbpubs.stanford.edu/pub/2002-12.
[8] G. Jeh and J. Widom. SimRank: A measure of
structural-context similarity. In Proceedings of the Eighth
ACM SIGKDD International Conference on Knowledge
Discovery and Data Mining, Edmonton, Alberta, Canada,
July 2002.
[9] J. M. Kleinberg. Authoritative sources in a hyperlinked
environment. In Proceedings of the Ninth Annual
ACM-SIAM Symposium on Discrete Algorithms, San
Francisco, California, Jan. 1998.
[10] R. Motwani and P. Raghavan. Randomized Algorithms.
Cambridge University Press, United Kingdom, 1995.
[11] L. Page, S. Brin, R. Motwani, and T. Winograd. The
PageRank citation ranking: Bringing order to the Web.
Technical report, Stanford University Database Group, 1998.
http://citeseer.nj.nec.com/368196.html.
[12] M. Richardson and P. Domingos. The intelligent surfer:
Probabilistic combination of link and content information in
PageRank. In Proceedings of Advances in Neural
Information Processing Systems 14, Cambridge,
Massachusetts, Dec. 2002.
279