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: hebc879f13b5e795e
Venue: PODS
Year: 2008
Pagerank: 0.00010737378
Overall Rank: 1,415 | 90.49%
DOI: 10.1145/1376916.1376928

Incoming Non-self Citations Over Time

Authors

1. Atish Das Sarma (Georgia Institute of Technology)
2. Sreenivas Gollapudi (Microsoft)
3. Rina Panigrahy (Microsoft)

BibTeX Citation

@inproceedings{sarma_pods08,
        address = {New York, NY, USA},
        series = {{PODS} '08},
        title = {{Estimating PageRank on Graph Streams}},
        url = {https://dl.acm.org/doi/10.1145/1376916.1376928},
        doi = {10.1145/1376916.1376928},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Sarma, Atish Das and Gollapudi, Sreenivas and Panigrahy, Rina},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
556	Fast Incremental and Personalized PageRank	2011	VLDB	0.00016500392
962	Fast Personalized PageRank on MapReduce	2011	SIGMOD	0.00012820478
2,420	gSketch: On Query Estimation in Graph Streams	2012	VLDB	8.4898523e-05
4,575	On Sampling from Massive Graph Streams	2017	VLDB	6.5256176e-05
4,777	Tornado: A System For Real-Time Iterative Analysis Over Evolving Data	2016	SIGMOD	6.4184698e-05
12,441	Tracking the Conductance of Rapidly Evolving Topic-Subgraphs	2015	VLDB	4.9793485e-05
12,595	Approximate Computation and Implicit Regularization for Very Large-scale Data Analysis	2012	PODS	4.9793485e-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
83	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00035978046
450	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD	0.00018032912
462	Counting Triangles in Data Streams	2006	PODS	0.00017807125
2,054	Space Efficient Mining of Multigraph Streams	2005	PODS	9.1135465e-05
5,698	Approximate Quantiles and the Order of the Stream	2006	PODS	6.0317949e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,033	Efficient Estimation of Heat Kernel PageRank for Local Clustering	2019	SIGMOD
2	4,264	Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme	2023	SIGMOD
3	1,368	Computing Personalized PageRank Quickly by Exploiting Graph Structures	2014	VLDB
4	962	Fast Personalized PageRank on MapReduce	2011	SIGMOD
5	8,379	PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs	2019	SIGMOD
6	8,226	Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches	2023	SIGMOD
7	556	Fast Incremental and Personalized PageRank	2011	VLDB
8	9,558	Efficient and Accurate PageRank Approximation on Large Graphs	2024	SIGMOD
9	6,403	Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach	2022	SIGMOD
10	8,227	Estimating Single-Node PageRank in O~(min{d_t, sqrt(m)}) Time	2023	VLDB