Dynamic PageRank: Additive Error and Batch Recomputation

on YouTube ↗51m

" summary

Shows a proof that maintaining a constant-factor multiplicative PageRank under n updates is provably hard: any algorithm must take at least n^(1−ε) total time for any ε>0 even with only insertions, resolving a 13-year open problem. Proposes additive L1 approximation in near-linear total time by capping walk lengths and sampling, and demonstrates a pragmatic batch recomputation (periodic full recompute) that, on standard temporal graphs, matches accuracy while running up to two orders of magnitude faster than dynamic walk-maintenance baselines.

AI-written summary · about

" chapters (14)

1. 0:00Introduction
2. 4:17Dynamic PageRank defined
3. 7:50Lower bounds
4. 11:09Additive error and batch recomputation
5. 15:46Prior work review
6. 18:00Random walk sampling
7. 22:20Additive approximation algorithms
8. 26:28Batch recomputation details
9. 33:02Empirical evaluation
10. 37:40Why batch recomputation wins
11. 39:50Open problems
12. 43:25Making algorithms practical
13. 44:28Summary
14. 45:12Q&A