<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body dir="auto"><div>Talk starting at 2pm in 402...</div><div><br></div><blockquote type="cite"><div><b>From:</b> Jennifer Rexford <<a href="mailto:jrex@CS.Princeton.EDU">jrex@CS.Princeton.EDU</a>><br><b>Date:</b> August 25, 2014 at 11:57:34 AM EDT<br><b>To:</b> <a href="mailto:talks@lists.cs.princeton.edu">talks@lists.cs.princeton.edu</a><br><b>Subject:</b> <b>[talks] 2-3pm Fri Aug 29 talk on scaling social search</b><br><br></div></blockquote><blockquote type="cite"><div><meta http-equiv="Content-Type" content="text/html charset=us-ascii">Speaker: <a href="http://web.stanford.edu/~sidb/">Siddhartha Bannerjee</a><br><div class="gmail_quote"><div dir="ltr"><div class="gmail_quote"><div dir="ltr"><p>Title: Scaling Social Search - PageRank Estimation for Large Networks<br></p><p>When and Where: 29th August (Friday) at 2:00 PM in Room 402 in the CS bldg.</p><div>Abstract:<br></div><p dir="ltr">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.</p><p dir="ltr">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.</p><p dir="ltr">Joint work with Peter Lofgren, Ashish Goel and C. Seshadri. Paper available at <a href="http://arxiv.org/abs/1404.3181" target="_blank">http://arxiv.org/abs/1404.3181</a>.</p></div></div></div></div></div></blockquote><blockquote type="cite"><div><span>_______________________________________________</span><br><span>talks mailing list</span><br><span><a href="mailto:talks@lists.cs.princeton.edu">talks@lists.cs.princeton.edu</a></span><br><span>To edit subscription settings or remove yourself, use this link:</span><br><span><a href="https://lists.cs.princeton.edu/mailman/listinfo/talks">https://lists.cs.princeton.edu/mailman/listinfo/talks</a></span><br></div></blockquote></body></html>