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.00019507721
Overall Rank: 595 | 95.87%
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
486	Fast Incremental and Personalized PageRank	2011	VLDB	0.00022068545
886	Fast Personalized PageRank on MapReduce	2011	SIGMOD	0.00015597161
2,437	gSketch: On Query Estimation in Graph Streams	2012	VLDB	8.8231651e-05
4,898	On Sampling from Massive Graph Streams	2017	VLDB	5.8459467e-05
5,211	Tornado: A System For Real-Time Iterative Analysis Over Evolving Data	2016	SIGMOD	5.6284829e-05
11,951	Tracking the Conductance of Rapidly Evolving Topic-Subgraphs	2015	VLDB	4.1945683e-05
12,107	Approximate Computation and Implicit Regularization for Very Large-scale Data Analysis	2012	PODS	4.1945683e-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.00044744986
392	Counting Triangles in Data Streams	2006	PODS	0.00024556183
443	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD	0.00022996573
1,472	Space Efficient Mining of Multigraph Streams	2005	PODS	0.00011828662
4,031	Approximate Quantiles and the Order of the Stream	2006	PODS	6.5121141e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,702	Efficient Estimation of Heat Kernel PageRank for Local Clustering	2019	SIGMOD	5.36473e-05
5,655	Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme	2023	SIGMOD	5.387631e-05
1,821	Computing Personalized PageRank Quickly by Exploiting Graph Structures	2014	VLDB	0.00010423565
886	Fast Personalized PageRank on MapReduce	2011	SIGMOD	0.00015597161
8,236	PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs	2019	SIGMOD	4.553296e-05
9,325	Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches	2023	SIGMOD	4.3556432e-05
486	Fast Incremental and Personalized PageRank	2011	VLDB	0.00022068545
9,214	Efficient and Accurate PageRank Approximation on Large Graphs	2024	SIGMOD	4.3716847e-05
7,086	Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach	2022	SIGMOD	4.8381004e-05
9,328	Estimating Single-Node PageRank in O~(min{d_t, sqrt(m)}) Time	2023	VLDB	4.3556432e-05