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: 1446
Venue: PODS
Year: 2008
Pagerank: 0.00010921308
Overall Rank: 1,396 | 90.43%
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.00016564032
945	Fast Personalized PageRank on MapReduce	2011	SIGMOD	0.00013066956
2,377	gSketch: On Query Estimation in Graph Streams	2012	VLDB	8.6710302e-05
4,613	On Sampling from Massive Graph Streams	2017	VLDB	6.6071509e-05
4,686	Tornado: A System For Real-Time Iterative Analysis Over Evolving Data	2016	SIGMOD	6.5620646e-05
12,149	Tracking the Conductance of Rapidly Evolving Topic-Subgraphs	2015	VLDB	5.093636e-05
12,304	Approximate Computation and Implicit Regularization for Very Large-scale Data Analysis	2012	PODS	5.093636e-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
82	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00036378991
443	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD	0.00018373044
458	Counting Triangles in Data Streams	2006	PODS	0.0001810876
2,013	Space Efficient Mining of Multigraph Streams	2005	PODS	9.3068345e-05
5,604	Approximate Quantiles and the Order of the Stream	2006	PODS	6.1533846e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,913	Efficient Estimation of Heat Kernel PageRank for Local Clustering	2019	SIGMOD
2	4,714	Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme	2023	SIGMOD
3	1,339	Computing Personalized PageRank Quickly by Exploiting Graph Structures	2014	VLDB
4	945	Fast Personalized PageRank on MapReduce	2011	SIGMOD
5	8,212	PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs	2019	SIGMOD
6	8,062	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,373	Efficient and Accurate PageRank Approximation on Large Graphs	2024	SIGMOD
9	6,284	Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach	2022	SIGMOD
10	8,063	Estimating Single-Node PageRank in O~(min{d_t, sqrt(m)}) Time	2023	VLDB