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

Jennifer Rexford jrex at CS.Princeton.EDU
Fri Aug 29 13:46:27 EDT 2014

Talk starting at 2pm in 402...

> From: Jennifer Rexford <jrex at CS.Princeton.EDU>
> Date: August 25, 2014 at 11:57:34 AM EDT
> To: talks at 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 at lists.cs.princeton.edu
> To edit subscription settings or remove yourself, use this link:
> https://lists.cs.princeton.edu/mailman/listinfo/talks
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cs.princeton.edu/pipermail/talks/attachments/20140829/fc41abbd/attachment.html>

More information about the talks mailing list