DBScholar

Back to papers

Efficient Algorithms for Finding Approximate Heavy Hitters in Personalized PageRanks

Summary: BLOG targets heavy-hitter PPR queries: pairwise AHH, reverse AHH, and multi-source reverse AHH. By combining Monte-Carlo sampling with backward propagation and logarithmic bucketing to handle high in-degree nodes, it beats SOTA on all three queries. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
5627
Venue
SIGMOD
Year
2018
Pagerank
6.1029326e-05
Overall Rank
5,741 | 60.62%
DOI
10.1145/3183713.3196919

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{wang_sigmod18,
        title = {{Efficient Algorithms for Finding Approximate Heavy Hitters in Personalized PageRanks}},
        author = {Wang, Sibo and Tao, Yufei},
        series = {{SIGMOD} '18},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3183713.3196919},
        url = {https://dl.acm.org/doi/10.1145/3183713.3196919},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank Citing Paper Year Venue Pagerank
3,892 Massively Parallel Algorithms for Personalized PageRank 2021 VLDB 7.0430255e-05
4,714 Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme 2023 SIGMOD 6.5497309e-05
6,284 Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach 2022 SIGMOD 5.927015e-05
7,142 Efficient Dynamic Weighted Set Sampling and Its Extension 2024 VLDB 5.6917227e-05
7,807 Efficient Approximate Algorithms for Empirical Entropy and Mutual Information 2021 SIGMOD 5.5404259e-05
8,062 Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches 2023 SIGMOD 5.4949527e-05
8,212 PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs 2019 SIGMOD 5.4658632e-05
8,911 Efficient and Provable Effective Resistance Computation on Large Graphs: an Index-based Approach 2024 SIGMOD 5.3483178e-05
9,373 Efficient and Accurate PageRank Approximation on Large Graphs 2024 SIGMOD 5.2755515e-05
10,186 Accelerating Approximate Analytical Join Queries over Unstructured Data with Statistical Guarantees 2026 SIGMOD 5.093636e-05
11,418 Efficient Approximation Framework for Attribute Recommendation 2023 SIGMOD 5.093636e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

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

Rank Cited Paper Year Venue Pagerank
945 Fast Personalized PageRank on MapReduce 2011 SIGMOD 0.00013066956
1,339 Computing Personalized PageRank Quickly by Exploiting Graph Structures 2014 VLDB 0.00011112799
1,769 BEAR: Block Elimination Approach for Random Walk with Restart on Large Graphs 2015 SIGMOD 9.7969398e-05
2,073 BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart 2017 SIGMOD 9.2209912e-05
2,225 HubPPR: Effective Indexing for Approximate Personalized PageRank 2017 VLDB 8.9183159e-05
2,362 Incremental and Accuracy-Aware Personalized PageRank through Scheduled Approximation 2013 VLDB 8.6889619e-05
3,315 Distributed Algorithms on Exact Personalized PageRank 2017 SIGMOD 7.5274958e-05
5,031 Link Spam Detection Based on Mass Estimation 2006 VLDB 6.3953025e-05
5,250 Parallel Personalized PageRank on Dynamic Graphs 2018 VLDB 6.2992176e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 9,046 One Index for All: Towards Efficient Personalized PageRank Computation for Every Damping Factor 2026 SIGMOD
2 9,373 Efficient and Accurate PageRank Approximation on Large Graphs 2024 SIGMOD
3 2,225 HubPPR: Effective Indexing for Approximate Personalized PageRank 2017 VLDB
4 2,173 Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push 2021 SIGMOD
5 2,362 Incremental and Accuracy-Aware Personalized PageRank through Scheduled Approximation 2013 VLDB
6 1,339 Computing Personalized PageRank Quickly by Exploiting Graph Structures 2014 VLDB
7 4,714 Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme 2023 SIGMOD
8 5,139 Edge-based Local Push for Personalized PageRank 2022 VLDB
9 8,062 Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches 2023 SIGMOD
10 6,284 Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach 2022 SIGMOD