document: To randomize or not to randomize : space optimal summaries for hyperlink analysis 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 .
doc_bio_tags: O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O