| Skip to main content | Skip to navigation |

Register Now!

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

Other items being presented by these speakers

Organised by

ECS Logo

in association with

BCS Logo ACM Logo

Platinum Sponsors

Sponsor of The CIO Dinner


Become a sponsor or exhibitor
Valid XHTML 1.0! IFIP logo WWW Conference Committee logo Web Consortium logo Valid CSS!