DBScholar

Back to papers

Memory-Aware Framework for Efficient Second-Order Random Walk on Large Graphs

Summary: Memory-aware framework for second-order random walks on billion-edge graphs, addressing memory blowups of conventional sampling with a cost model for node sampling. Acceptance-rejection sampling with per-node cost optimization allocates under a memory budget while minimizing time, delivering ~90% memory reduction and practical APIs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
5837
Venue
SIGMOD
Year
2020
Pagerank
5.8813146e-05
Overall Rank
6,423 | 55.94%
DOI
10.1145/3318464.3380562

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{shao_sigmod20,
        title = {{Memory-Aware Framework for Efficient Second-Order Random Walk on Large Graphs}},
        author = {Shao, Yingxia and Huang, Shiyue and Miao, Xupeng and Cui, Bin and Chen, Lei},
        series = {{SIGMOD} '20},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3318464.3380562},
        url = {https://dl.acm.org/doi/10.1145/3318464.3380562},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank Citing Paper Year Venue Pagerank
6,003 ThunderRW: An In-Memory Graph Random Walk Engine 2021 VLDB 6.0130964e-05
7,201 An I/O-Efficient Disk-based Graph System for Scalable Second-Order Random Walk of Large Graphs 2022 VLDB 5.6755554e-05
7,255 Space-Efficient Random Walks on Streaming Graphs 2023 VLDB 5.662517e-05
11,228 FlowWalker: A Memory-efficient and High-performance GPU-based Dynamic Graph Random Walk Framework 2024 VLDB 5.093636e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank Cited Paper Year Venue Pagerank
3 Pregel: A System for Large-Scale Graph Processing 2010 SIGMOD 0.0012250108
32 Hive - A Warehousing Solution Over a Map-Reduce Framework 2009 VLDB 0.00050111008
290 An Overview of Query Optimization in Relational Systems 1998 PODS 0.0002227038
294 Graphs-at-a-time: Query Language and Access Methods for Graph Databases 2008 SIGMOD 0.00022253507
352 On Graph Query Optimization in Large Networks 2010 VLDB 0.00020375193
735 Profiling, What-if Analysis, and Cost-based Optimization of MapReduce Programs 2011 VLDB 0.00014522606
4,216 An Efficient Similarity Search Framework for SimRank over Large Dynamic Graphs 2015 VLDB 6.8273894e-05
5,002 Remember Where You Came From: On The Second-Order Random Walk Based Proximity Measures 2017 VLDB 6.4066378e-05
5,687 Walk, Not Wait: Faster Sampling Over Online Social Networks 2015 VLDB 6.1211881e-05
6,044 Exploiting Soft and Hard Correlations in Big Data Query Optimization 2016 VLDB 5.995949e-05
6,634 An Experimental Evaluation of SimRank-based Similarity Search Algorithms 2017 VLDB 5.8182573e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 4,572 On the Embeddability of Random Walk Distances 2013 VLDB
2 5,687 Walk, Not Wait: Faster Sampling Over Online Social Networks 2015 VLDB
3 5,002 Remember Where You Came From: On The Second-Order Random Walk Based Proximity Measures 2017 VLDB
4 6,003 ThunderRW: An In-Memory Graph Random Walk Engine 2021 VLDB
5 7,255 Space-Efficient Random Walks on Streaming Graphs 2023 VLDB
6 4,216 An Efficient Similarity Search Framework for SimRank over Large Dynamic Graphs 2015 VLDB
7 1,958 A General Framework for Estimating Graphlet Statistics via Random Walk 2017 VLDB
8 11,228 FlowWalker: A Memory-efficient and High-performance GPU-based Dynamic Graph Random Walk Framework 2024 VLDB
9 4,497 Leveraging History for Faster Sampling of Online Social Networks 2015 VLDB
10 7,201 An I/O-Efficient Disk-based Graph System for Scalable Second-Order Random Walk of Large Graphs 2022 VLDB