Estimating Single-Node PageRank in O~(min{d_t, sqrt(m)}) Time
Summary: Introduces SetPush, a single-node PageRank estimator for undirected graphs that avoids the linear-time worst cases of random walks and backward push. It achieves \tilde O(min{d_t,√m}) time with constant relative error and failure probability, supported by experiments. (summarized by gpt-5.6-luna on Jul 24 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Hanzhi Wang (Renmin University of China)
- 2. Zhewei Wei (Renmin University of China)
BibTeX Citation
@article{wang_vldb23,
title = {{Estimating Single-Node PageRank in O\~{}(min\{d\_t, sqrt(m)\}) Time}},
author = {Wang, Hanzhi and Wei, Zhewei},
journal = {PVLDB},
series = {{VLDB} '23},
volume = {16},
number = {11},
pages = {2949--2961},
doi = {10.14778/3611479.3611500},
url = {https://doi.org/10.14778/3611479.3611500},
year = {2023}
}Incoming Citations (Sorted by Pagerank)
Showing 2 of 2 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 10,161 | Near-Optimality for Single-Source Personalized PageRank | 2026 | PODS | 5.093636e-05 |
| 11,237 | BIRD: Efficient Approximation of Bidirectional Hidden Personalized PageRank | 2024 | VLDB | 5.093636e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 5 of 5 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 285 | ObjectRank: Authority-Based Keyword Search in Databases | 2004 | VLDB | 0.00022365284 |
| 556 | Fast Incremental and Personalized PageRank | 2011 | VLDB | 0.00016564032 |
| 4,024 | TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs | 2018 | SIGMOD | 6.9479974e-05 |
| 5,913 | Efficient Estimation of Heat Kernel PageRank for Local Clustering | 2019 | SIGMOD | 6.0439971e-05 |
| 8,212 | PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs | 2019 | SIGMOD | 5.4658632e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 5,913 | Efficient Estimation of Heat Kernel PageRank for Local Clustering | 2019 | SIGMOD |
| 2 | 556 | Fast Incremental and Personalized PageRank | 2011 | VLDB |
| 3 | 5,826 | Realtime Index-Free Single Source SimRank Processing on Web-Scale Graphs | 2020 | VLDB |
| 4 | 6,284 | Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach | 2022 | SIGMOD |
| 5 | 8,212 | PRSim: Sublinear Time SimRank Computation on Large Power-Law Graphs | 2019 | SIGMOD |
| 6 | 8,062 | Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches | 2023 | SIGMOD |
| 7 | 9,373 | Efficient and Accurate PageRank Approximation on Large Graphs | 2024 | SIGMOD |
| 8 | 2,173 | Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push | 2021 | SIGMOD |
| 9 | 5,139 | Edge-based Local Push for Personalized PageRank | 2022 | VLDB |
| 10 | 1,396 | Estimating PageRank on Graph Streams | 2008 | PODS |