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: h05d9a8793979839f
Venue: SIGMOD
Year: 2018
Pagerank: 5.9682458e-05
Overall Rank: 5,859 | 60.61%
DOI: 10.1145/3183713.3196919

Incoming Non-self Citations Over Time

Authors

1. Sibo Wang (University of Queensland)
2. Yufei Tao (Chinese University of Hong Kong)

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,977	Massively Parallel Algorithms for Personalized PageRank	2021	VLDB	6.8850687e-05
4,264	Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme	2023	SIGMOD	6.6978776e-05
6,403	Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach	2022	SIGMOD	5.7963998e-05
7,246	Efficient Dynamic Weighted Set Sampling and Its Extension	2024	VLDB	5.5750011e-05
7,965	Efficient Approximate Algorithms for Empirical Entropy and Mutual Information	2021	SIGMOD	5.4161136e-05
8,226	Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches	2023	SIGMOD	5.3740319e-05
8,379	PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs	2019	SIGMOD	5.3432239e-05
8,629	Efficient and Provable Effective Resistance Computation on Large Graphs: an Index-based Approach	2024	SIGMOD	5.2994494e-05
9,558	Efficient and Accurate PageRank Approximation on Large Graphs	2024	SIGMOD	5.1571823e-05
10,402	Accelerating Approximate Analytical Join Queries over Unstructured Data with Statistical Guarantees	2026	SIGMOD	4.9793485e-05
11,732	Efficient Approximation Framework for Attribute Recommendation	2023	SIGMOD	4.9793485e-05

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
962	Fast Personalized PageRank on MapReduce	2011	SIGMOD	0.00012820478
1,368	Computing Personalized PageRank Quickly by Exploiting Graph Structures	2014	VLDB	0.0001090624
1,798	BEAR: Block Elimination Approach for Random Walk with Restart on Large Graphs	2015	SIGMOD	9.616919e-05
2,102	BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart	2017	SIGMOD	9.0463758e-05
2,258	HubPPR: Effective Indexing for Approximate Personalized PageRank	2017	VLDB	8.7385422e-05
2,393	Incremental and Accuracy-Aware Personalized PageRank through Scheduled Approximation	2013	VLDB	8.5321273e-05
3,266	Distributed Algorithms on Exact Personalized PageRank	2017	SIGMOD	7.4775e-05
5,123	Link Spam Detection Based on Mass Estimation	2006	VLDB	6.2632748e-05
5,300	Parallel Personalized PageRank on Dynamic Graphs	2018	VLDB	6.1896851e-05

Semantically Similar Papers

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