A Survey on Personalized PageRank Computation Algorithms <s> D. DYNAMIC PROGRAMMING <s> Recent web search techniques augment traditional text matching with a global notion of "importance" based on the linkage structure of the web, such as in Google's PageRank algorithm. For more refined searches, this global notion of importance can be specialized to create personalized views of importance--for example, importance scores can be biased according to a user-specified set of initially-interesting pages. Computing and storing all possible personalized views in advance is impractical, as is computing personalized 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 construction of personalized views from partial vectors is practical at query time. We present efficient dynamic programming algorithms for computing partial vectors, an algorithm for constructing personalized views from partial vectors, and experimental results demonstrating the effectiveness and scalability of our techniques. <s> BIB001 </s> A Survey on Personalized PageRank Computation Algorithms <s> D. DYNAMIC PROGRAMMING <s> Personalized PageRank expresses link-based page quality around user selected pages. The only previous personalized PageRank algorithm that can serve on-line queries for an unrestricted choice of pages on large graphs is our Monte Carlo algorithm [WAW 2004]. In this paper we achieve unrestricted personalization by combining rounding and randomized sketching techniques in the dynamic programming algorithm of Jeh and Widom [WWW 2003]. We evaluate the precision of approximation experimentally on large scale real-world data and find significant improvement over previous results. As a key theoretical contribution we show that our algorithms use an optimal amount of space by also improving earlier asymptotic worst-case lower bounds. Our lower bounds and algorithms apply to the SimRank as well; of independent interest is the reduction of the SimRank computation to personalized PageRank. <s> BIB002
The dynamic programming method for PPR utilizes the decomposition theorem BIB001 . The most basic algorithm repeatedly updates the process using the decomposition theorem until PPR vectors converge. for all n i . 3) Repeat step 2 until it converges. Fig. 3 . illustrates how the dynamic programming algorithm updates PPR vectors. Like the bookmark coloring algorithm, dynamic programming also updates vectors by repetitively applying the decomposition theorem. However, unlike the bookmark coloring algorithm, dynamic programming updates every PPR − → v i simultaneously. This algorithm can be applied to the Fully Personalized PageRank problem since it simultaneously produces the PPR − → v i s from every node; however, it requires a large space to store the intermediate results. To reduce the space requirement, two methods are applied: rounding and sketching BIB002 . The rounding technique optimizes its space requirement by rounding all values down to a multiple of the prescribed error value . With the rounding technique, the basic version of dynamic programming changes to the following one. for all n i . 4. Repeat steps 2 and 3 until k = 2 log 1−c . The function ψ k represents the rounding down to k . This algorithm guarantees for all is and js. In the second one, sketching is a hash based approach that utilizes the randomize data structure with low dimensions. It dramatically reduces the space requirement; however, it takes far longer and does not guarantee the error bound. In the empirical evaluation, the dynamic programming algorithm with rounding solves the fully Personalized PageRank problem on a graph with 80M nodes in 2.25 days, and it takes 6 days with rounding and sketching. In summary, these optimization techniques achieve impressive spatial performance gain; however, it is hard to say that they are efficient enough to process large graphs in terms of the time.