[talks] 2-3pm Fri Aug 29 talk on scaling social search

[Jennifer Rexford]

Speaker: Siddhartha Bannerjee
Title: Scaling Social Search - PageRank Estimation for Large Networks

When and Where: 29th August (Friday) at 2:00 PM in Room 402 in the CS bldg.

Abstract:
Although effective search is one of the great successes of the internet, social search lags far behind. A major hurdle is the complexity of existing algorithms for estimating Personalized PageRank -- a generalization of PageRank which measures centrality with respect to a fixed node in a network. In particular, to estimate PageRank values up to the required accuracies, existing algorithms need time which scales linearly in the network size -- this renders them infeasible for real-time social search.

In this talk, I will present FAST-PPR, the first algorithm for Personalized PageRank estimation with an average running-time guarantee which is sublinear in the network size. This speedup is achieved via a combination of linear algebraic techniques and random walks; this new approach may prove useful in other estimation problems on networks. Moreover, I'll present detailed empirical studies on numerous large networks, wherein FAST-PPR dramatically outperforms existing algorithms -- for example, with target nodes sampled according to popularity, on the 2010 Twitter graph with 1.5 billion edges, FAST-PPR has a 160 factor speedup compared to the state-of-the-art.

Joint work with Peter Lofgren, Ashish Goel and C. Seshadri. Paper available at http://arxiv.org/abs/1404.3181.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cs.princeton.edu/pipermail/talks/attachments/20140825/bd6351f2/attachment.html>