Minimal MapReduce Algorithms
Summary: Introduces the 'minimal algorithm' notion for MapReduce, optimizing load balancing, space, CPU, I/O, and network cost within a small constant factor. Shows existence of elegant minimal algorithms for fundamental database problems, validated by extensive experiments. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Yufei Tao (Chinese University of Hong Kong; Korea Advanced Institute of Science and Technology)
- 2. Wenqing Lin (Nanyang Technological University)
- 3. Xiaokui Xiao (Nanyang Technological University)
BibTeX Citation
@inproceedings{tao_sigmod13,
title = {{Minimal MapReduce Algorithms}},
author = {Tao, Yufei and Lin, Wenqing and Xiao, Xiaokui},
series = {{SIGMOD} '13},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/2463676.2463719},
url = {https://dl.acm.org/doi/10.1145/2463676.2463719},
year = {2013}
}Incoming Citations (Sorted by Pagerank)
Showing 11 of 11 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,552 | Scalable Subgraph Enumeration in MapReduce | 2015 | VLDB | 0.00010379532 |
| 2,973 | Functional Dependencies for Graphs | 2016 | SIGMOD | 7.9083516e-05 |
| 3,008 | Scalable Big Graph Processing in MapReduce | 2014 | SIGMOD | 7.8578871e-05 |
| 3,065 | Pregel Algorithms for Graph Connectivity Problems with Performance Guarantees | 2014 | VLDB | 7.7989716e-05 |
| 5,599 | A Tight Lower Bound for Comparison-Based Quantile Summaries | 2020 | PODS | 6.154479e-05 |
| 5,878 | Distributed Graph Simulation: Impossibility and Possibility | 2014 | VLDB | 6.0539311e-05 |
| 7,151 | Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability | 2018 | VLDB | 5.6873519e-05 |
| 7,484 | On Scale Independence for Querying Big Data | 2014 | PODS | 5.6074278e-05 |
| 11,634 | Algorithms for a Topology-aware Massively Parallel Computation Model | 2021 | PODS | 5.093636e-05 |
| 12,036 | An Efficient MapReduce Cube Algorithm for Varied Data Distributions | 2016 | SIGMOD | 5.093636e-05 |
| 12,082 | Parallel Evaluation of Multi-Semi-Joins | 2016 | VLDB | 5.093636e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 36 of 36 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 1,257 | Automatic Optimization for MapReduce Programs | 2011 | VLDB |
| 2 | 735 | Profiling, What-if Analysis, and Cost-based Optimization of MapReduce Programs | 2011 | VLDB |
| 3 | 1,009 | Online Aggregation for Large MapReduce Jobs | 2011 | VLDB |
| 4 | 3,008 | Scalable Big Graph Processing in MapReduce | 2014 | SIGMOD |
| 5 | 1,514 | Upper and Lower Bounds on the Cost of a Map-Reduce Computation | 2013 | VLDB |
| 6 | 2,265 | A Platform for Scalable One-Pass Analytics using MapReduce | 2011 | SIGMOD |
| 7 | 72 | Map-Reduce-Merge: Simplified Relational Data Processing on Large Clusters | 2007 | SIGMOD |
| 8 | 1,436 | The Performance of MapReduce: An In-depth Study | 2010 | VLDB |
| 9 | 44 | A Comparison of Approaches to Large-Scale Data Analysis | 2009 | SIGMOD |
| 10 | 3,163 | Multi-Query Optimization in MapReduce Framework | 2014 | VLDB |