Database Paper Browser

Back to papers

Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches

Summary: Two variance-reduction techniques for Personalized PageRank: power-iteration variance reduction and progressive sampling. Integrates these with random-walk and spanning-forest Monte Carlo PPR to achieve higher accuracy at equal or lower runtime than state-of-the-art bidirectional algorithms, leveraging historical sampling. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
6664
Venue
SIGMOD
Year
2023
Pagerank
4.351469e-05
Overall Rank
9,330 | 35.16%
DOI
10.1145/3589305

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank Citing Paper Year Venue Pagerank
10,028 One Index for All: Towards Efficient Personalized PageRank Computation for Every Damping Factor 2026 SIGMOD 4.1905499e-05
10,960 Efficient and Provable Effective Resistance Computation on Large Graphs: an Index-based Approach 2024 SIGMOD 4.1905499e-05
11,030 BIRD: Efficient Approximation of Bidirectional Hidden Personalized PageRank 2024 VLDB 4.1905499e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 16 of 16 cited papers.

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

Rank Cited Paper Year Venue Pagerank
1,626 Fast and Exact Top-k Search for Random Walk with Restart 2012 VLDB 0.0001108491
1,809 Computing Personalized PageRank Quickly by Exploiting Graph Structures 2014 VLDB 0.00010472588
2,076 Efficient Ad-hoc Search for Personalized PageRank 2013 SIGMOD 9.6057342e-05
2,110 HubPPR: Effective Indexing for Approximate Personalized PageRank 2017 VLDB 9.5280826e-05
2,189 BEAR: Block Elimination Approach for Random Walk with Restart on Large Graphs 2015 SIGMOD 9.3358152e-05
2,515 BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart 2017 SIGMOD 8.6115215e-05
2,522 Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push 2021 SIGMOD 8.6029608e-05
2,745 Incremental and Accuracy-Aware Personalized PageRank through Scheduled Approximation 2013 VLDB 8.1831695e-05
3,600 Parallel Local Graph Clustering 2016 VLDB 6.9285467e-05
3,853 Distributed Algorithms on Exact Personalized PageRank 2017 SIGMOD 6.6987268e-05
4,560 Massively Parallel Algorithms for Personalized PageRank 2021 VLDB 6.0788254e-05
4,688 TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs 2018 SIGMOD 5.9900111e-05
5,693 Parallel Personalized PageRank on Dynamic Graphs 2018 VLDB 5.3683002e-05
6,310 Efficient Algorithms for Finding Approximate Heavy Hitters in Personalized PageRanks 2018 SIGMOD 5.111823e-05
6,866 Indexed Fast Network Proximity Querying 2018 VLDB 4.8994824e-05
7,081 Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach 2022 SIGMOD 4.833459e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
4,560 Massively Parallel Algorithms for Personalized PageRank 2021 VLDB 6.0788254e-05
6,310 Efficient Algorithms for Finding Approximate Heavy Hitters in Personalized PageRanks 2018 SIGMOD 5.111823e-05
10,028 One Index for All: Towards Efficient Personalized PageRank Computation for Every Damping Factor 2026 SIGMOD 4.1905499e-05
2,745 Incremental and Accuracy-Aware Personalized PageRank through Scheduled Approximation 2013 VLDB 8.1831695e-05
5,693 Parallel Personalized PageRank on Dynamic Graphs 2018 VLDB 5.3683002e-05
1,809 Computing Personalized PageRank Quickly by Exploiting Graph Structures 2014 VLDB 0.00010472588
478 Fast Incremental and Personalized PageRank 2011 VLDB 0.00022183187
5,666 Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme 2023 SIGMOD 5.3824583e-05
875 Fast Personalized PageRank on MapReduce 2011 SIGMOD 0.00015679931
7,081 Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach 2022 SIGMOD 4.833459e-05