Towards Scaling Fully Personalized PageRank Export

@incollection{citeulike:1727484, abstract = {Personalized PageRank expresses backlink-based page quality around user-selected pages in a similar way as PageRank expresses quality over the entire Web. Existing personalized PageRank algorithms can however serve on-line queries only for a restricted choice of page selection. In this paper we achieve full personalization by a novel algorithm that computes a compact database of simulated random walks; this database can serve arbitrary personal choices of small subsets of web pages. We prove that for a fixed error probability, the size of our database is linear in the number of web pages. We justify our estimation approach by asymptotic worst-case lower bounds; we show that exact personalized PageRank values can only be obtained from a database of quadratic size.}, author = {Fogaras, D\'{a}niel and R\'{a}cz, Bal\'{a}zs}, citeulike-article-id = {1727484}, citeulike-linkout-0 = {http://www.springerlink.com/content/nr8y6a19796uedef}, journal = {Algorithms and Models for the Web-Graph}, keywords = {pagerank, random-walk}, pages = {105--117}, posted-at = {2008-09-06 00:02:42}, priority = {2}, title = {Towards Scaling Fully Personalized PageRank}, url = {http://www.springerlink.com/content/nr8y6a19796uedef}, year = {2004} }

TY - CHAP ID - citeulike:1727484 L3 - citeulike-article-id:1727484 N2 - Personalized PageRank expresses backlink-based page quality around user-selected pages in a similar way as PageRank expresses quality over the entire Web. Existing personalized PageRank algorithms can however serve on-line queries only for a restricted choice of page selection. In this paper we achieve full personalization by a novel algorithm that computes a compact database of simulated random walks; this database can serve arbitrary personal choices of small subsets of web pages. We prove that for a fixed error probability, the size of our database is linear in the number of web pages. We justify our estimation approach by asymptotic worst-case lower bounds; we show that exact personalized PageRank values can only be obtained from a database of quadratic size. JF - Algorithms and Models for the Web-Graph EP - 117 TI - Towards Scaling Fully Personalized PageRank SP - 105 KW - pagerank KW - random-walk AU - Fogaras, Dániel AU - Rácz, Balázs PY - 2004/// UR - http://www.springerlink.com/content/nr8y6a19796uedef ER -