Themes
	Business Success
	next wave
	education & science
	security
	health

To Randomize or Not To Randomize: Space Optimal Summaries for Hyperlink Analysis

Tamás Sarlsó, Computer and Automation Research Institute, Hungarian Academy of Sciences (MTA SZTAKI) AND Eötvös University, Budapest, Hungary
András A. Benczúr, Computer and Automation Research Institute, Hungarian Academy of Sciences, Hungary
Károly Csalogány, Computer and Automation Research Institute, Hungarian Academy of Sciences, Hungary
Dániel Fogaras, Computer and Automation Research Institute, Hungarian Academy of Sciences (MTA SZTAKI) AND Budapest University of Technology and Economics, Hungary
Balázs Rácz, Computer and Automation Research Institute, Hungarian Academy of Sciences (MTA SZTAKI) AND Budapest University of Technology and Economics, Hungary

Full text:

Presentation Slides:

Track: Search

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 SimRank as well; of independent interest is the reduction of the SimRank computation to personalized PageRank.

Citation

Sarlós, T., Benczúr, A. A., Csalogány, K., Fogaras, D., and Rácz, B. 2006. To randomize or not to randomize: space optimal summaries for hyperlink analysis. In Proceedings of the 15th International Conference on World Wide Web (Edinburgh, Scotland, May 23 - 26, 2006). WWW '06. ACM Press, New York, NY, 297-306.
DOI= http://doi.acm.org/10.1145/1135777.1135823