FrogWild! – Fast PageRank Approximations on Graph Engines

Summary: FrogWild! fast PageRank approximations via quantized power iteration with parallel random walks. Partial GraphLab mirror sync cuts cross-node traffic, induces walk correlations; bound shows near-PageRank accuracy; faster, up to 7x on Twitter. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11386
Venue: VLDB
Year: 2015
Pagerank: 5.6839455e-05
Overall Rank: 7,171 | 50.81%
DOI: 10.14778/2757807.2757812

Incoming Non-self Citations Over Time

Authors

1. Ioannis Mitliagkas (University of Texas)
2. Michael Borokhovich (University of Texas)
3. Alexandros G. Dimakis (University of Texas)
4. Constantine Caramanis (University of Texas)

BibTeX Citation

@article{mitliagkas_vldb15,
        title = {{FrogWild! – Fast PageRank Approximations on Graph Engines}},
        author = {Mitliagkas, Ioannis and Borokhovich, Michael and Dimakis, Alexandros G. and Caramanis, Constantine},
        journal = {PVLDB},
        series = {{VLDB} '15},
        volume = {8},
        number = {8},
        pages = {874--885},
        doi = {10.14778/2757807.2757812},
        url = {https://doi.org/10.14778/2757807.2757812},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,073	BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart	2017	SIGMOD	9.2209912e-05
4,089	TCUDB: Accelerating Database with Tensor Processors	2022	SIGMOD	6.9096857e-05
11,842	Ariadne: Online Provenance for Big Graph Analytics	2019	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 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
1,654	Navigating the Maze of Graph Analytics Frameworks using Massive Graph Datasets	2014	SIGMOD	0.00010104703

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,063	Estimating Single-Node PageRank in O~(min{d_t, sqrt(m)}) Time	2023	VLDB
2	4,225	Realtime Top-k Personalized PageRank over Large Graphs on GPUs	2020	VLDB
3	4,024	TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs	2018	SIGMOD
4	2,173	Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push	2021	SIGMOD
5	1,339	Computing Personalized PageRank Quickly by Exploiting Graph Structures	2014	VLDB
6	2,362	Incremental and Accuracy-Aware Personalized PageRank through Scheduled Approximation	2013	VLDB
7	945	Fast Personalized PageRank on MapReduce	2011	SIGMOD
8	6,284	Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach	2022	SIGMOD
9	1,396	Estimating PageRank on Graph Streams	2008	PODS
10	556	Fast Incremental and Personalized PageRank	2011	VLDB