Database Paper Browser

Back to papers

Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach

Summary: Introduces spanning-forests sampling for personalized PageRank via loop-erased alpha-random walks, grounded in a new matrix forest theorem. Alpha-insensitive, fast single-source and single-target PPR queries; outperforms prior methods with experiments on seven large real-world graphs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
6452
Venue
SIGMOD
Year
2022
Pagerank
4.8381004e-05
Overall Rank
7,086 | 50.71%
DOI
10.1145/3514221.3526140

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank Citing Paper Year Venue Pagerank
7,446 QTCS: Efficient Query-Centered Temporal Community Search 2024 VLDB 4.727813e-05
9,214 Efficient and Accurate PageRank Approximation on Large Graphs 2024 SIGMOD 4.3716847e-05
9,245 Efficient Resistance Distance Computation: the Power of Landmark-based Approaches 2023 SIGMOD 4.3690661e-05
9,325 Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches 2023 SIGMOD 4.3556432e-05
9,484 Enabling Window-Based Monotonic Graph Analytics with Reusable Transitional Results for Pattern-Consistent Queries 2024 VLDB 4.3341665e-05
9,642 Efficient Index Maintenance for Effective Resistance Computation on Evolving Graphs 2025 SIGMOD 4.3109001e-05
10,028 One Index for All: Towards Efficient Personalized PageRank Computation for Every Damping Factor 2026 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 12 of 12 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
4,733 TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs 2018 SIGMOD 5.9631943e-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
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
6,309 Efficient Algorithms for Finding Approximate Heavy Hitters in Personalized PageRanks 2018 SIGMOD 5.1167347e-05
6,381 Edge-based Local Push for Personalized PageRank 2022 VLDB 5.0890757e-05
595 Estimating PageRank on Graph Streams 2008 PODS 0.00019507721
3,872 Distributed Algorithms on Exact Personalized PageRank 2017 SIGMOD 6.6785582e-05
886 Fast Personalized PageRank on MapReduce 2011 SIGMOD 0.00015597161
2,780 Incremental and Accuracy-Aware Personalized PageRank through Scheduled Approximation 2013 VLDB 8.1317773e-05
10,028 One Index for All: Towards Efficient Personalized PageRank Computation for Every Damping Factor 2026 SIGMOD 4.1945683e-05
1,821 Computing Personalized PageRank Quickly by Exploiting Graph Structures 2014 VLDB 0.00010423565
5,655 Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme 2023 SIGMOD 5.387631e-05
9,325 Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches 2023 SIGMOD 4.3556432e-05