Estimating PageRank on Graph Streams

Summary: Streaming algorithms to estimate l-step random-walk distributions, mixing time and conductance using sublinear memory and few passes. Applies to PageRank: computes additive-ε approximations in sublinear space (e.g., Õ(n M^{-4/3})) and Õ(M^{4/3}) passes for mixing time M, outperforming the O(n)-space, O(M)-pass baseline when M is large. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1447
Venue: PODS
Year: 2008
Pagerank: 0.00019569121
Overall Rank: 589 | 95.91%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
478	Fast Incremental and Personalized PageRank	2011	VLDB	0.00022183187
875	Fast Personalized PageRank on MapReduce	2011	SIGMOD	0.00015679931
2,439	gSketch: On Query Estimation in Graph Streams	2012	VLDB	8.8181328e-05
4,903	On Sampling from Massive Graph Streams	2017	VLDB	5.8403259e-05
5,215	Tornado: A System For Real-Time Iterative Analysis Over Evolving Data	2016	SIGMOD	5.6231911e-05
11,959	Tracking the Conductance of Rapidly Evolving Topic-Subgraphs	2015	VLDB	4.1905499e-05
12,115	Approximate Computation and Implicit Regularization for Very Large-scale Data Analysis	2012	PODS	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
126	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00044753012
389	Counting Triangles in Data Streams	2006	PODS	0.00024649634
446	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD	0.00023002059
1,466	Space Efficient Mining of Multigraph Streams	2005	PODS	0.00011838607
4,024	Approximate Quantiles and the Order of the Stream	2006	PODS	6.5177066e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,713	Efficient Estimation of Heat Kernel PageRank for Local Clustering	2019	SIGMOD	5.3595796e-05
5,666	Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme	2023	SIGMOD	5.3824583e-05
1,809	Computing Personalized PageRank Quickly by Exploiting Graph Structures	2014	VLDB	0.00010472588
875	Fast Personalized PageRank on MapReduce	2011	SIGMOD	0.00015679931
8,231	PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs	2019	SIGMOD	4.5489304e-05
9,330	Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches	2023	SIGMOD	4.351469e-05
478	Fast Incremental and Personalized PageRank	2011	VLDB	0.00022183187
9,216	Efficient and Accurate PageRank Approximation on Large Graphs	2024	SIGMOD	4.3674946e-05
7,081	Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach	2022	SIGMOD	4.833459e-05
9,333	Estimating Single-Node PageRank in O~(min{d_t, sqrt(m)}) Time	2023	VLDB	4.351469e-05