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
6663
Venue
SIGMOD
Year
2023
Pagerank
4.3556432e-05
Overall Rank
9,325 | 35.13%
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.1945683e-05
10,957 Efficient and Provable Effective Resistance Computation on Large Graphs: an Index-based Approach 2024 SIGMOD 4.1945683e-05
11,027 BIRD: Efficient Approximation of Bidirectional Hidden Personalized PageRank 2024 VLDB 4.1945683e-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,641 Fast and Exact Top-k Search for Random Walk with Restart 2012 VLDB 0.00011047924
1,821 Computing Personalized PageRank Quickly by Exploiting Graph Structures 2014 VLDB 0.00010423565
2,098 Efficient Ad-hoc Search for Personalized PageRank 2013 SIGMOD 9.5480012e-05
2,210 BEAR: Block Elimination Approach for Random Walk with Restart on Large Graphs 2015 SIGMOD 9.2856573e-05
2,242 HubPPR: Effective Indexing for Approximate Personalized PageRank 2017 VLDB 9.218875e-05
2,537 BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart 2017 SIGMOD 8.5834428e-05
2,780 Incremental and Accuracy-Aware Personalized PageRank through Scheduled Approximation 2013 VLDB 8.1317773e-05
2,827 Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push 2021 SIGMOD 8.0551884e-05
3,597 Parallel Local Graph Clustering 2016 VLDB 6.9345175e-05
3,872 Distributed Algorithms on Exact Personalized PageRank 2017 SIGMOD 6.6785582e-05
4,562 Massively Parallel Algorithms for Personalized PageRank 2021 VLDB 6.0846728e-05
4,733 TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs 2018 SIGMOD 5.9631943e-05
5,680 Parallel Personalized PageRank on Dynamic Graphs 2018 VLDB 5.3734643e-05
6,309 Efficient Algorithms for Finding Approximate Heavy Hitters in Personalized PageRanks 2018 SIGMOD 5.1167347e-05
6,865 Indexed Fast Network Proximity Querying 2018 VLDB 4.9041884e-05
7,086 Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach 2022 SIGMOD 4.8381004e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
4,562 Massively Parallel Algorithms for Personalized PageRank 2021 VLDB 6.0846728e-05
6,309 Efficient Algorithms for Finding Approximate Heavy Hitters in Personalized PageRanks 2018 SIGMOD 5.1167347e-05
10,028 One Index for All: Towards Efficient Personalized PageRank Computation for Every Damping Factor 2026 SIGMOD 4.1945683e-05
2,780 Incremental and Accuracy-Aware Personalized PageRank through Scheduled Approximation 2013 VLDB 8.1317773e-05
5,680 Parallel Personalized PageRank on Dynamic Graphs 2018 VLDB 5.3734643e-05
1,821 Computing Personalized PageRank Quickly by Exploiting Graph Structures 2014 VLDB 0.00010423565
486 Fast Incremental and Personalized PageRank 2011 VLDB 0.00022068545
5,655 Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme 2023 SIGMOD 5.387631e-05
886 Fast Personalized PageRank on MapReduce 2011 SIGMOD 0.00015597161
7,086 Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach 2022 SIGMOD 4.8381004e-05