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: 5775
Venue: SIGMOD
Year: 2020
Pagerank: 5.0392468e-05
Overall Rank: 6,498 | 54.80%
DOI: 10.1145/3318464.3380562

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,058	ThunderRW: An In-Memory Graph Random Walk Engine	2021	VLDB	5.2310254e-05
7,212	Space-Efficient Random Walks on Streaming Graphs	2023	VLDB	4.7989929e-05
7,363	An I/O-Efficient Disk-based Graph System for Scalable Second-Order Random Walk of Large Graphs	2022	VLDB	4.7523184e-05
11,017	FlowWalker: A Memory-efficient and High-performance GPU-based Dynamic Graph Random Walk Framework	2024	VLDB	4.1945683e-05

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
4	Pregel: A System for Large-Scale Graph Processing	2010	SIGMOD	0.0019005923
70	Hive - A Warehousing Solution Over a Map-Reduce Framework	2009	VLDB	0.00059533166
454	An Overview of Query Optimization in Relational Systems	1998	PODS	0.00022734812
461	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00022499343
506	On Graph Query Optimization in Large Networks	2010	VLDB	0.00021475362
868	Profiling, What-if Analysis, and Cost-based Optimization of MapReduce Programs	2011	VLDB	0.00015789681
4,791	An Efficient Similarity Search Framework for SimRank over Large Dynamic Graphs	2015	VLDB	5.9188595e-05
5,177	Remember Where You Came From: On The Second-Order Random Walk Based Proximity Measures	2017	VLDB	5.6439245e-05
5,730	Walk, Not Wait: Faster Sampling Over Online Social Networks	2015	VLDB	5.3506029e-05
6,173	Exploiting Soft and Hard Correlations in Big Data Query Optimization	2016	VLDB	5.1699414e-05
6,789	An Experimental Evaluation of SimRank-based Similarity Search Algorithms	2017	VLDB	4.9251746e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,527	On the Embeddability of Random Walk Distances	2013	VLDB	6.1083926e-05
5,730	Walk, Not Wait: Faster Sampling Over Online Social Networks	2015	VLDB	5.3506029e-05
6,058	ThunderRW: An In-Memory Graph Random Walk Engine	2021	VLDB	5.2310254e-05
5,177	Remember Where You Came From: On The Second-Order Random Walk Based Proximity Measures	2017	VLDB	5.6439245e-05
7,212	Space-Efficient Random Walks on Streaming Graphs	2023	VLDB	4.7989929e-05
4,791	An Efficient Similarity Search Framework for SimRank over Large Dynamic Graphs	2015	VLDB	5.9188595e-05
1,740	A General Framework for Estimating Graphlet Statistics via Random Walk	2017	VLDB	0.0001071792
11,017	FlowWalker: A Memory-efficient and High-performance GPU-based Dynamic Graph Random Walk Framework	2024	VLDB	4.1945683e-05
2,108	Leveraging History for Faster Sampling of Online Social Networks	2015	VLDB	9.5327714e-05
7,363	An I/O-Efficient Disk-based Graph System for Scalable Second-Order Random Walk of Large Graphs	2022	VLDB	4.7523184e-05