1 Introduction
The idea of using hyperlink mining algorithms in Web search engines appears since the beginning of the success of Google's PageRank [24]. Hyperlink based methods are based on the assumption that a hyperlink implies that page votes for as a quality page. In this paper we address the computational issues [13,17,11,12] of personalized PageRank [24] and SimRank [16].
Personalized PageRank (PPR) [24] enters user preferences by assigning more importance to the neighborhood of pages at the user's selection. Jeh and Widom [16] introduced SimRank, the multistep linkbased similarity function with the recursive idea that two pages are similar if pointed to by similar pages. Notice that both measures are hard to compute over massive graphs: naive personalization would require on the fly power iteration over the entire graph for a user query; naive SimRank computation would require power iteration over all pairs of vertices.
We give algorithms with provable performance guarantees based on computation with sketches [7] as well as simple deterministic summaries; see Table 1 for a comparison of our methods with previous approaches. We may personalize to any single page from which arbitrary page set personalization follows by linearity [13]. Similarly, by our SimRank algorithm we may compute the similarity of any two pages or the similarity top list of any single page. Motivated by search engine applications, we give twophase algorithms that first compute a compact database from which value or top list queries can be answered with a low number of accesses. Our key results are summarized as follows:
 We give practical methods for serving unrestricted online personalized PageRank (Section 2.1) as well as SimRank queries with space a reasonable constant per vertex (Section 3). The methods are based on deterministic rounding.
 We give a theoretically optimal algorithm for personalized PageRank value queries (Section 2.2) based on randomized sketching. Given an additive error and the probability of an incorrect result, we improve the disk usage bound from [11,12] to .
 We give theoretically optimal algorithms for SimRank value and top list queries (Section 3.1) by a nontrivial reduction of SimRank to personalized PageRank.
 We improve the communication complexity based lower
bounds of [11,12] for the size of the database (Section 4); our bounds are matched by our algorithms. Our sketchbased algorithms use optimal space; surprisingly for top list queries deterministic rounding is already optimal in itself.  In Section 5 we experimentally analyze the precision of approximation over the Stanford WebBase graph and conclude that our summaries provide better approximation for the top personalized PageRank scores than previous methods.
1.1 Related Results
The scalable computation of personalized PageRank was addressed by several papers [13,18,17] that gradually increase the choice for personalization. By Haveliwala's method [13] we may personalize to the combination of 16 topics extracted from the Open Directory Project. The BlockRank algorithm of Kamvar et al. [18] speeds up personalization to the combination of hosts. The state of the art Hub Decomposition algorithm of Jeh and Widom [17] computed and encoded personalization vectors for approximately 100K personalization pages.
To the best of our knowledge, the only scalable personalized PageRank algorithm that supports the unrestricted choice of the teleportation vector is the Monte Carlo method of [11]. This algorithm samples the personalized PageRank distribution of each page simultaneously during the precomputation phase, and estimates the personalized PageRank scores from the samples at query time. The drawback of the sampling approach is that approximate scores are returned, where the error of approximation depends on the random choice. In addition the bounds involve the unknown variance, which can in theory be as large as , and hence we need random samples. Indeed a matching sampling complexity lower bound for telling binomial distributions with means apart [1] indicates that one can not reduce the number of samples when approximating personalized PageRank. Similar findings of the superiority of summarization or sketching over sampling is described in [5]. The algorithms presented in Section 2 outperform the Monte Carlo method by significantly reducing the error.
We also address the computational issues of SimRank, a linkbased similarity function introduced by Jeh and Widom [16]. The power iteration SimRank algorithm of [16] is not scalable since it iterates on a quadratic number of values, one for each pair of Web pages; in [16] experiments on graphs with no more than 300K vertices are reported. Analogously to personalized PageRank, the scalable computation of SimRank was first achieved by sampling [12]. Our new SimRank approximation algorithms presented in Section 3 improve the precision of computation.
The key idea of our algorithms is that we use lossy representation of large vectors either by rounding or sketching. Sketches are compact randomized data structures that enable approximate computation in low dimension. To be more precise, we adapt the CountMin Sketch of Cormode and Muthukrishnan [7], which was primarily introduced for data stream computation. We use sketches for small space computation; in the same spirit Palmer et al. [25] apply probabilistic counting sketches to approximate the sizes of neighborhoods of vertices in large graphs. Further sketching techniques for data streams are surveyed in [23]. Lastly we mention that CountMin Sketch and the historically first sketch, the Bloom filter [2] stem from the same idea; we refer to the detailed survey [4] for further variations and applications.
Surprisingly, it turns out that sketches do not help if the top highest ranked or most similar nodes are queried; the deterministic version of our algorithms show the same performance as the randomized without even allowing a small probability of returning a value beyond the error bound. Here the novelty is the optimal performance of the deterministic method; the top problem is known to cause difficulties in sketchbased methods and always increases sketch sizes by a factor of . By using times larger space we may use a binary search structure or we may use sketches accessed times per query [7]. Note that queries require an error probability of that again increase sketch sizes by a factor of .
In Section 4 we show that our algorithms build optimal sized databases. To obtain lower bounds on the database size, we apply communication complexity techniques that are commonly used for space lower bounds [21]. Our reductions are somewhat analogous to those applied by Henzinger et al. [14] for space lower bounds on stream graph computation.
1.2 Preliminaries
We briefly introduce notation, and recall definitions and basic facts about PageRank, SimRank and the CountMin sketch.
Personalized PageRank
Let us consider the web as a graph. Let denote the number of vertices and the number edges. Let and denote the number of edges leaving and entering , respectively. Details of handling nodes with and are omitted.
In [24] the PageRank vector , ..., is defined as the solution of the following equation , where , ..., is the teleportation vector and is the teleportation probability with a typical value of . If is uniform, i.e. for all , then is the PageRank. For nonuniform the solution is called personalized PageRank; we denote it by PPR. Since PPR is linear in [13,17], it can be computed by linear combination of personalization to single points , i.e. to vectors consisting of all 0 except for node where . Let PPRPPR.
An alternative characterization of PPR [10,17] is based on the probability that a length random walk starting at node ends in node . We obtain PPR by choosing random according to the geometric distribution:
PPR  (1) 
PPR PPR  (2) 
PPR PPR  (3) 
PPR PPR  (4) 
SimRank
Jeh and Widom [16] define SimRank by the following equation very similar to the PageRank power iteration such that Sim and
Sim  (5) 
CountMin Sketch
The CountMin Sketch [7] is a compact randomized approximate representation of nonnegative vector , ..., such that a single value can be queried with a fixed additive error and a probability of returning a value out of this bound. The representation is a table of depth and width . One row of the table is computed with a random hash function . The ^{th} entry of the row is defined as . Then the CountMin sketch table of consists of such rows with hash functions chosen uniformly at random from a pairwiseindependent family.
CountMin sketches are based on the principle that any randomized approximate computation with one sided error and bias can be turned into an algorithm that has guaranteed error at most with probability by running parallel copies and taking the minimum. The proof simply follows from Markov's inequality and is described for the special cases of sketch value and inner product in the proofs of Theorems 1 and 2 of [7], respectively.
2 Personalized PageRank
We give two efficient realizations of the dynamic programming algorithm of Jeh and Widom [17]. Our algorithms are based on the idea that if we use an approximation for the partial values in certain iteration, the error will not aggregate when summing over outedges, instead the error of previous iterations will decay with the power of . Our first algorithm in Section 2.1 uses certain deterministic rounding optimized for smallest runtime for a given error, while our second algorithm in Section 2.2 is based on CountMin sketches [7].
The original implementation of dynamic programming [17] relies on the observation that in the first iterations of dynamic programming only vertices within distance have nonzero value. However, the rapid expansion of the neighborhoods increases disk requirement close to after a few iterations, which limits the usability of this approach^{2}. Furthermore, an external memory implementation would require significant additional disk space.
We may justify why dynamic programming is the right choice for smallspace computation by comparing dynamic programming to power iteration over the graph of Fig. 1. When computing PPR, power iteration moves topdown, starting at , stepping into its neighbors and finally adding up all their values at . Hence when approximating, we accumulate all error when entering the large indegree node and in particular we must compute PPR values fairly exact. Dynamic programming, in contrast, moves bottom up by computing the trivial PPR vector, then all the PPR, then finally averages all of them into PPR. Because of averaging we do not amplify error at large indegrees; even better by looking at (4) we notice that the effect of earlier steps diminishes exponentially in . In particular even if there are edges entering from further nodes, we may safely discard all the small PPR values for further computations, thus saving space over power iteration where we require the majority of these values in order to compute PPR with little error.
We measure the performance of our algorithms in the sense of intermediate disk space usage. Notice that our algorithms are twophase in that they preprocess the graph to a compact database from which value and top list queries can be served realtime; preprocessing space and time is hence crucial for a search engine application. Surprisingly, in this sense rounding in itself yields an optimal algorithm for top list queries as shown by giving a matching lower bound in Section 4. The sketching algorithm further improves space usage by a factor of and is hence optimal for single value queries. For finding top lists, however, we need additional techniques such as binary searching as in [7] that loose the factor gain and use asymptotically the same amount of space as the deterministic algorithm. Since the deterministic rounding involves no probability of giving an incorrect answer, that algorithm is superior for top list queries.
The key to the efficiency of our algorithms is the use of small size approximate values obtained either by rounding and handling sparse vectors or by computing over sketches. In order to perform the update step of Algorithm 1 we must access all vectors; the algorithm proceeds as if we were multiplying the weighted adjacency matrix for with the vector parallel for all values of . We may use (semi)external memory algorithms [27]; efficiency will depend on the size of the description of the vectors.
The original algorithm of Jeh and Widom defined by equation (4) uses two vectors in the implementation. We remark that a single vector suffices since by using updated values within an iteration we only speed convergence up. A similar argument is given by McSherry [22] for the power iteration, however there the resulting sequential update procedure still requires two vectors.
2.1 Rounding
In Algorithm 1 we compute the steps of the dynamic programming personalized PageRank algorithm (4) by rounding all values down to a multiple of the prescribed error value . As the sum of PPR for all equals one, the rounded nonzeroes can be stored in small space since there may be at most of them.
We improve on the trivial observation that there are at most rounded nonzero values in two ways as described in the next two theorems. First, we observe that the effect of early iterations decays as the power of in the iterations, allowing us to similarly increase the approximation error for early iterations . We prove correctness in Theorem 2; later in Theorem 4 it turns out that this choice also weakens the dependency of the running time on the number of iterations. Second, we show that the size of the nonzeroes can be efficiently bitencoded in small space; while this observation is less relevant for a practical implementation, this is key in giving an algorithm that matches the lower bound of Section 4.
Since we use a single vector in the implementation, we may
update a value by values that have themselves already been
updated in iteration . Nevertheless since
and
hence decreases in , values that have earlier been updated in
the current iteration in fact incur an error smaller than
required on the right hand side of the update step of Algorithm
1. In order to distinguish values
before and after a single step of the update, let us use
to denote values on the
right hand side. To prove, notice that by the Decomposition
Theorem (3)
PPR  
PPR 
PPR 
Next we show that multiples of that sum up to 1 can be stored in bit space. For the exact result we need to select careful but simple encoding methods given in the trivial lemma below.
2.2 Sketching
Next we give a sketch version of Algorithm 1 that improves the space requirement of the rounding based version by a factor of , thus matches the lower bound of Section 4 for value queries. First we give a basic algorithm that uses uniform error bound in all iterations and is not optimized for storage size in bits. Then we show how to gradually decrease approximation error to speed up earlier iterations with less effect on final error; finally we obtain the space optimal algorithm by the bit encoding of Lemma 3.
The key idea is that we replace each PPR vector with its constant size CountMin sketch in the dynamic programming iteration (4). Let denote the sketching operator that replaces a vector by the table as in Section 1.2 and let us perform the iterations of (4) with SPPR and . Since the sketching operator is trivially linear, in iteration we obtain the sketch of the next temporary vector SPPR from the sketches SPPR.
To illustrate the main ingredients, we give the simplest form of a sketchbased algorithm with error, space and time analysis. Let us perform the iterations of (4) with wide and deep sketches times; then by Theorem 1 and the linearity of sketching we can estimate PPR for all from SPPR with additive error and error probability . The personalized PageRank database consists of sketch tables SPPR for all . The data occupies machine words, since we have to store tables of reals. An update for node takes time by averaging tables of size and adding , each in time. Altogether the required iterations run in time.
Next we weaken the dependence of the running time on the number of iterations by gradually decreasing error as in Section 2.1. When decreasing the error in sketches, we face the problem of increasing hash table sizes as the iterations proceed. Since there is no way to efficiently rehash data into larger tables, we approximate personalized PageRank slightly differently by representing the end distribution of length walks, PPR, with their rounded sketches in the pathsumming formula (2):
(6) 
(7) 
We err for three reasons: we do not run the iteration infinitely; in iteration we round values down by at most , causing a deterministic negative error; and finally the CountMin Sketch uses hashing, causing a random positive error. For bounding these errors, imagine running iteration (7) without the rounding function but still with wide and deep sketches and denote its results by SPPR and define
Finally we lower bound ; the bound is deterministic. The loss due to rounding down in iteration affects all subsequent iterations, and hence
3 SimRank
In this section first we give a simpler algorithm for serving SimRank value and toplist queries that combines rounding with the empirical fact that there are relatively few large values in the similarity matrix. Then in Section 3.1 we give an algorithm for SimRank values that uses optimal storage in the sense of the lower bounds of Section 4. Of independent interest is the main component of the algorithm that reduces SimRank to the computation of values similar to personalized PageRank.
SimRank and personalized PageRank are similar in that they both fill an matrix when the exact values are computed. Another similarity is that practical queries may ask for the maximal elements within a row. Unlike personalized PageRank however, when rows can be easily sketched and iteratively computed over approximate values, the matrix structure is lost within the iterations for Sim as we may have to access values of arbitrary Sim. Even worse PPR while
In practice is expected be a reasonable constant times
.
Hence first we present a simple direct algorithm that finds the
largest values within the entire
Sim table. In order to give a rounded
implementation of the iterative SimRank equation (5), we need to give an efficient algorithm to
compute a single iteration. The naive implementation requires
time for each edge pair with a common
source vertex that may add up to
. Instead for
we will compute the next iteration
with the help of an intermediate step when edges out of only one
of the two vertices are considered:
ASim  Sim  (8)  
Sim  ASim  (9) 
Along the same line as the proof of Theorems 2 we prove that (i) by rounding values in iterations (89) we approximate values with small additive error; (ii) the output of the algorithm occupies small space; and (iii) approximate top lists can be efficiently answered from the output. The proof is omitted due to space limitations. We remark here that (89) can be implemented by 4 external memory sorts per iteration, in two of which the internal space usage can in theory grow arbitrary large even compared to . This is due to the fact that we may round only once after each iteration; hence if for some large outdegree node a value Sim is above the rounding threshold or ASim becomes positive, then we have to temporarily store positive values for all outneighbors, most of which will be discarded when rounding.
 (i)

The algorithm returns approximate values for with
Sim.  (ii)

The space used by the
values is
bits
where
Sim.
 (iii)
 Top list queries can be answered after positive values are sorted for each in time.
3.1 Reduction of SimRank to PPR
Now we describe a SimRank algorithm that uses a database of size matching the corresponding lower bound of Section 4 by taking advantage of the fact that large values of similarity appear in blocks of the similarity table. The blocking nature can be captured by observing the similarity of Sim to the product PPRPPR of vectors PPR and PPR.
We use the independent result of [10,17,16] that PageRank type values can be expressed by summing over endpoints of walks as in equation (1). First we express SimRank by walk pair sums, then we show how SimRank can be reduced to personalized PageRank by considering pairs of walks as products. Finally we give sketching and rounding algorithms for value and top queries based on this reduction.
In order to capture pairs of walks of equal length we define ``reversed'' PPR by using walks of length exactly by modifying (1):
RP  (10) 
(11) 
Next we formalize the relation and give an efficient algorithm that reduces SimRank to PPR on the reversed graph. As a ``step 0 try'' we consider
SimRPRP  (12) 
In order to exclude pairs of walks that meet before ending, we use the principle of inclusion and exclusion. We count pairs of walks that have at least meeting points after start as follows. Since after their first meeting point the walks proceed as if computing the similarity of to itself, we introduce a selfsimilarity measure by counting weighted pairs of walks that start at and terminate at the same vertex by extending (12):
SSim RP RP  (13) 
SSimRP RP SSim  (14) 
SimRP RP SSim  (15) 
Sim Sim Sim Sim  (16) 
Sim  RP RP SSim where  
SSim  SSim  (17) 
The proof of the main theorems below are omitted due to space
limitations.
4 Lower bounds
In this section we will prove lower bounds on the database size of approximate PPR algorithms that achieve personalization over a subset of vertices. More precisely we will consider twophase algorithms: in the first phase the algorithm has access to the edge set of the graph and has to compute a database; in the second phase the algorithm gets a query and has to answer by accessing the database, i.e. the algorithm cannot access the graph during querytime. A worst case lower bound on the database size holds, if for any twophase algorithm there exists a personalization input such that a database of size bits is built in the first phase.
We will consider the following queries for :

 value
approximation: given the vertices
approximate
with
such
that

top query: given
the vertex , with probability
compute the set of vertices which have
personalized PPR values according to vertex greater
than . Precisely we require the
following:
As Theorem 6 of [11] shows, any twophase PPR algorithm solving the exact ( ) PPR value problem requires an bit database. Our tool towards the lower bounds will be the asymmetric communication complexity game bitvector probing [14]: there are two players and ; player has a vector of bits; player has a number ; and they have to compute the function , i.e., the output is the ^{th} bit of the input vector . To compute the proper output they have to communicate, and communication is restricted in the direction . The oneway communication complexity [21] of this function is the number of transferred bits in the worst case by the best protocol.
Now we are ready to state and prove our lower bounds, which match the performance of the algorithms presented in Sections 2 and 3.1, hence showing that they are space optimal.
Given a vector of bits, constructs the ``bipartite'' graph with vertex set For the edge set, is partitioned into blocks, where each block contains bits for , . Notice that each can be regarded as a binary encoded number with . To encode into the graph, adds an edge iff , and also attaches a selfloop to each . Thus the edges outgoing from represent the blocks .
After constructing the graph computes an
 Doulike.com  online dating sites
 seattle dating
 houston dating
 chicago dating
 madison dating
 atlanta dating
 las vegas dating
 san diego dating
 mobile dating
 omaha dating
 dallas dating
 denver dating
 san antonio dating
 boston dating
 new york dating
 pittsburgh dating
 portland dating
 austin dating
 miami dating
 san francisco dating
 orlando dating
 charlotte dating
 milwaukee dating
 los angeles dating
 lake charles dating
 tampa dating
 phoenix dating
 nashville dating
 sacramento dating
 tucson dating
 el paso dating
 colorado springs dating
 huntsville dating
 tulsa dating
 spokane dating
 indianapolis dating
 albuquerque dating
 philadelphia dating
 cincinnati dating
 louisville dating
 knoxville dating
 minneapolis dating
 kansas city dating
 grand rapids dating
 new orleans dating
 san jose dating
 detroit dating
 cleveland dating
 boise dating
 asheville dating
 fort worth dating
 fresno dating
 reno dating
 baltimore dating
 myrtle beach dating
 wichita dating
 bakersfield dating
 memphis dating
 columbia dating
 salt lake city dating
 columbus dating
 charleston dating
 raleigh dating
 jacksonville dating
 pensacola dating
 ann arbor dating
 des moines dating
 corpus christi dating
 buffalo dating
 anchorage dating
 tallahassee dating
 sarasota dating
 toledo dating
 savannah dating
 chattanooga dating
 lubbock dating
 sioux falls dating
 baton rouge dating
 fargo dating
 honolulu dating
 odessa dating
 fort collins dating
 vancouver dating
 washington dating
 rochester dating
 fort wayne dating
 evansville dating
 virginia beach dating
 amarillo dating
 richmond dating
 oklahoma city dating
 eugene dating
 greenville dating
 syracuse dating
 mesa dating
 tacoma dating
 las cruces dating
 lansing dating
 modesto dating
 boulder dating
 gainesville dating
 kalamazoo dating
 hollywood dating
 greensboro dating
 muskegon dating
 naples dating
 shreveport dating
 dayton dating
 cedar rapids dating
 little rock dating
 green bay dating
 augusta dating
 women seeking for men
 ocala dating
 birmingham dating
 pueblo dating
 rockford dating
 abilene dating
 south bend dating
 midland dating
 akron dating
 topeka dating
 santa rosa dating
 flint dating
 college station dating
 fort myers dating
 scottsdale dating
 lincoln dating
 albany dating
 tuscaloosa dating
 long beach dating
 stamford dating
 west palm beach dating
 winston salem dating
 harrisburg dating
 fort lauderdale dating
 laredo dating
 new haven dating
 wichita falls dating
 bellevue dating
 berkeley dating
 palm bay dating
 temecula dating
 lafayette dating
 beaumont dating
 lakewood dating
 clarksville dating
 springfield dating
 lexington dating
 visalia dating
 billings dating
 canton dating
 murfreesboro dating
 elk grove dating
 peoria dating
 irvine dating
 santa maria dating
 ogden dating
 clearwater dating
 olathe dating
 stockton dating
 athens dating
 simi valley dating
 naperville dating
 gilbert dating
 cape coral dating
 lakeland dating
 newark dating
 plano dating
 killeen dating
 victorville dating
 bradenton dating
 thousand oaks dating
 pasadena dating
 baytown dating
 longview dating
 panama city dating
 fairfield dating
 wilmington dating
 overland park dating
 lancaster dating
 everett dating
 youngstown dating
 erie dating
 aurora dating
 worcester dating
 fayetteville dating
 beaverton dating
 boca raton dating
 conroe dating
 katy dating
 santa clarita dating
 ventura dating
 arlington dating
 macon dating
 hartford dating
 durham dating
 manchester dating
 providence dating
 oceanside dating
 riverside dating
 jersey city dating
 norfolk dating
 frisco dating
 carlsbad dating
 round rock dating
 spartanburg dating
 oakland dating
 marietta dating
 daytona beach dating
 cambridge dating
 roseville dating
 huntington beach dating
 chula vista dating
 fremont dating
 reading dating
 chandler dating
 hampton dating
 tempe dating
 tyler dating
 allentown dating
 decatur dating
 kissimmee dating
 montgomery dating
 garland dating