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:

Track: Search

Slot: 11:00-12:30, Thursday 25th May

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.

Other items being presented by these speakers

• Detecting Nepotistic Links by Language Model (Posters Track)