Back to papers
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)
Paper ID
h35532cf700e0ccfd
Venue
SIGMOD
Year
2013
Pagerank
8.2743492e-05
Overall Rank
2,561 | 82.84%
DOI
10.1145/2463676.2463719
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,565
Scalable Subgraph Enumeration in MapReduce 2015
VLDB
0.00010185615
2,894
Functional Dependencies for Graphs 2016
SIGMOD
7.8870146e-05
3,071
Scalable Big Graph Processing in MapReduce 2014
SIGMOD
7.6670408e-05
3,101
Pregel Algorithms for Graph Connectivity Problems with Performance Guarantees 2014
VLDB
7.6310428e-05
4,975
A Tight Lower Bound for Comparison-Based Quantile Summaries 2020
PODS
6.3194701e-05
5,968
Distributed Graph Simulation: Impossibility and Possibility 2014
VLDB
5.9135528e-05
7,324
Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability 2018
VLDB
5.5387994e-05
7,628
On Scale Independence for Querying Big Data 2014
PODS
5.4649494e-05
11,991
Algorithms for a Topology-aware Massively Parallel Computation Model 2021
PODS
4.9605343e-05
12,380
An Efficient MapReduce Cube Algorithm for Varied Data Distributions 2016
SIGMOD
4.9605343e-05
12,424
Parallel Evaluation of Multi-Semi-Joins 2016
VLDB
4.9605343e-05
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.
Rank
Cited Paper
Year
Venue
Pagerank
6
Pig Latin: A Not-So-Foreign Language for Data Processing 2008
SIGMOD
0.0010494385
30
SCOPE: Easy and Efficient Parallel Processing of Massive Data Sets 2008
VLDB
0.00050364918
49
Dremel: Interactive Analysis of Web-Scale Datasets 2010
VLDB
0.00043085722
120
HadoopDB: An Architectural Hybrid of MapReduce and DBMS Technologies for Analytical Workloads 2009
VLDB
0.00031017868
359
Efficient Parallel Set-Similarity Joins Using MapReduce 2010
SIGMOD
0.00019963275
560
Densest Subgraph in Streaming and MapReduce 2012
VLDB
0.00016408664
677
Hadoop++: Making a Yellow Elephant Run Like a Cheetah (Without It Even Noticing) 2010
VLDB
0.00014835154
759
Profiling, What-if Analysis, and Cost-based Optimization of MapReduce Programs 2011
VLDB
0.00014194746
799
A Comparison of Join Algorithms for Log Processing in MapReduce 2010
SIGMOD
0.00013839554
825
MRShare: Sharing Across Multiple Queries in MapReduce 2010
VLDB
0.00013600553
867
Processing Theta-Joins using MapReduce* 2011
SIGMOD
0.00013342302
876
Tenzing: A SQL Implementation On The MapReduce Framework 2011
VLDB
0.00013272245
963
Fast Personalized PageRank on MapReduce 2011
SIGMOD
0.00012805146
982
Parallel Evaluation of Conjunctive Queries 2011
PODS
0.00012687016
1,022
Online Aggregation for Large MapReduce Jobs 2011
VLDB
0.00012400958
1,040
Jaql: A Scripting Language for Large Scale Semistructured Data Analysis 2011
VLDB
0.00012336829
1,286
Automatic Optimization for MapReduce Programs 2011
VLDB
0.00011187304
1,360
SkewTune: Mitigating Skew in MapReduce Applications 2012
SIGMOD
0.00010893993
1,424
V-SMART-Join: A Scalable MapReduce Framework for All-Pair Similarity Joins of Multisets and Vectors 2012
VLDB
0.00010694144
1,691
ParaTimer: A Progress Indicator for MapReduce DAGs 2010
SIGMOD
9.838545e-05
1,706
PerfXplain: Debugging MapReduce Job Performance 2012
VLDB
9.804657e-05
1,850
Cheetah: A High Performance, Custom Data Warehouse on Top of MapReduce 2010
VLDB
9.4997173e-05
1,936
ReStore: Reusing Results of MapReduce Jobs 2012
VLDB
9.3375824e-05
2,183
Efficient Processing of k Nearest Neighbor Joins using MapReduce 2012
VLDB
8.8973287e-05
2,532
Stubby: A Transformation-based Optimizer for MapReduce Workflows 2012
VLDB
8.3132509e-05
2,615
PLANET: Massively Parallel Learning of Tree Ensembles with MapReduce 2009
VLDB
8.2019215e-05
2,699
CoHadoop: Flexible Data Placement and Its Exploitation in Hadoop 2011
VLDB
8.100024e-05
2,908
Social Content Matching in MapReduce 2011
VLDB
7.8645705e-05
2,918
Column-Oriented Storage Techniques for MapReduce 2011
VLDB
7.8517976e-05
2,944
Efficient Multi-way Theta-Join Processing Using MapReduce 2012
VLDB
7.8126906e-05
3,017
Llama: Leveraging Columnar Storage for Scalable Join Processing in the MapReduce Framework 2011
SIGMOD
7.7319353e-05
3,154
Early Accurate Results for Advanced Analytics on MapReduce 2012
VLDB
7.5708527e-05
3,164
Energy Management for MapReduce Clusters 2010
VLDB
7.5607087e-05
3,787
M3R: Increased Performance for In-Memory Hadoop Jobs 2012
VLDB
6.9994582e-05
4,159
Behavioral Simulations in MapReduce 2010
VLDB
6.7595949e-05
5,664
Building Wavelet Histograms on Large Data in MapReduce 2012
VLDB
6.0293278e-05
Semantically Similar Papers