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

Talk starting at 2pm in 402...

From: Jennifer Rexford Date: August 25, 2014 at 11:57:34 AM EDT To: talks@lists.cs.princeton.edu Subject: [talks] 2-3pm Fri Aug 29 talk on scaling social search

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.

_______________________________________________ talks mailing list talks@lists.cs.princeton.edu To edit subscription settings or remove yourself, use this link: https://lists.cs.princeton.edu/mailman/listinfo/talks