DBScholar

Back to papers

BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart

Summary: BePI uses block-elimination preprocessing and a preconditioned iterative solver to scale RWR on billion-edge graphs. Fast queries and low memory come from nonzero reduction and preconditioning, enabling 100x larger graphs with 130x less memory and 9x faster RWR. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
5378
Venue
SIGMOD
Year
2017
Pagerank
9.2209912e-05
Overall Rank
2,073 | 85.78%
DOI
10.1145/3035918.3035950

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{jung_sigmod17,
        title = {{BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart}},
        author = {Jung, Jinhong and Park, Namyong and Sael, Lee and Kang, U},
        series = {{SIGMOD} '17},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3035918.3035950},
        url = {https://dl.acm.org/doi/10.1145/3035918.3035950},
        year = {2017}
}

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank Citing Paper Year Venue Pagerank
2,173 Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push 2021 SIGMOD 9.0375634e-05
3,892 Massively Parallel Algorithms for Personalized PageRank 2021 VLDB 7.0430255e-05
4,024 TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs 2018 SIGMOD 6.9479974e-05
4,225 Realtime Top-k Personalized PageRank over Large Graphs on GPUs 2020 VLDB 6.821373e-05
4,714 Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme 2023 SIGMOD 6.5497309e-05
5,741 Efficient Algorithms for Finding Approximate Heavy Hitters in Personalized PageRanks 2018 SIGMOD 6.1029326e-05
5,960 On Graph Representation for Attributed Hypergraph Clustering 2025 SIGMOD 6.0274692e-05
6,284 Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach 2022 SIGMOD 5.927015e-05
7,861 Efficient Resistance Distance Computation: the Power of Landmark-based Approaches 2023 SIGMOD 5.5302333e-05
8,062 Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches 2023 SIGMOD 5.4949527e-05
8,188 Efficient and Effective Attributed Hypergraph Clustering via K-Nearest Neighbor Augmentation 2023 SIGMOD 5.4703528e-05
9,046 One Index for All: Towards Efficient Personalized PageRank Computation for Every Damping Factor 2026 SIGMOD 5.3251649e-05
9,769 Efficient Index Maintenance for Effective Resistance Computation on Evolving Graphs 2025 SIGMOD 5.2209769e-05
11,390 Effective and Efficient PageRank-based Positioning for Graph Visualization 2023 SIGMOD 5.093636e-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
556 Fast Incremental and Personalized PageRank 2011 VLDB 0.00016564032
758 Simrank++: Query Rewriting through Link Analysis of the Click Graph 2008 VLDB 0.00014277369
945 Fast Personalized PageRank on MapReduce 2011 SIGMOD 0.00013066956
1,365 Scalable Similarity Search for SimRank 2014 SIGMOD 0.00011017467
1,414 Fast and Exact Top-k Search for Random Walk with Restart 2012 VLDB 0.00010848387
1,628 Fast and Unified Local Search for Random Walk Based K-Nearest-Neighbor Query in Large Graphs 2014 SIGMOD 0.00010186757
1,769 BEAR: Block Elimination Approach for Random Walk with Restart on Large Graphs 2015 SIGMOD 9.7969398e-05
1,812 Efficient SimRank-based Similarity Join Over Large Graphs 2013 VLDB 9.6948178e-05
1,838 Efficient Ad-hoc Search for Personalized PageRank 2013 SIGMOD 9.6436348e-05
3,177 Computing PageRank in a Distributed Internet Search System 2004 VLDB 7.6633723e-05
5,815 Reverse Top-k Search using Random Walk with Restart 2014 VLDB 6.0777346e-05
7,171 FrogWild! – Fast PageRank Approximations on Graph Engines 2015 VLDB 5.6839455e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 5,432 Scalable and Effective Bipartite Network Embedding 2022 SIGMOD
2 4,216 An Efficient Similarity Search Framework for SimRank over Large Dynamic Graphs 2015 VLDB
3 7,201 An I/O-Efficient Disk-based Graph System for Scalable Second-Order Random Walk of Large Graphs 2022 VLDB
4 11,228 FlowWalker: A Memory-efficient and High-performance GPU-based Dynamic Graph Random Walk Framework 2024 VLDB
5 4,572 On the Embeddability of Random Walk Distances 2013 VLDB
6 10,240 Fast Estimation of Pairwise Biharmonic Distance on Graphs 2026 SIGMOD
7 3,951 READS: A Random Walk Approach for Efficient and Accurate Dynamic SimRank 2017 VLDB
8 5,815 Reverse Top-k Search using Random Walk with Restart 2014 VLDB
9 6,423 Memory-Aware Framework for Efficient Second-Order Random Walk on Large Graphs 2020 SIGMOD
10 1,769 BEAR: Block Elimination Approach for Random Walk with Restart on Large Graphs 2015 SIGMOD