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.2782871e-05
Overall Rank
2,573 | 82.71%
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,572
Scalable Subgraph Enumeration in MapReduce 2015
VLDB
0.0001019315
3,027
Functional Dependencies for Graphs 2016
SIGMOD
7.7351194e-05
3,068
Scalable Big Graph Processing in MapReduce 2014
SIGMOD
7.6841028e-05
3,109
Pregel Algorithms for Graph Connectivity Problems with Performance Guarantees 2014
VLDB
7.6384672e-05
5,326
A Tight Lower Bound for Comparison-Based Quantile Summaries 2020
PODS
6.1794406e-05
5,955
Distributed Graph Simulation: Impossibility and Possibility 2014
VLDB
5.9331392e-05
7,306
Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability 2018
VLDB
5.5571749e-05
7,612
On Scale Independence for Querying Big Data 2014
PODS
5.4829143e-05
11,947
Algorithms for a Topology-aware Massively Parallel Computation Model 2021
PODS
4.9769913e-05
12,337
An Efficient MapReduce Cube Algorithm for Varied Data Distributions 2016
SIGMOD
4.9769913e-05
12,381
Parallel Evaluation of Multi-Semi-Joins 2016
VLDB
4.9769913e-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.0010515896
30
SCOPE: Easy and Efficient Parallel Processing of Massive Data Sets 2008
VLDB
0.00050475202
49
Dremel: Interactive Analysis of Web-Scale Datasets 2010
VLDB
0.0004314366
120
HadoopDB: An Architectural Hybrid of MapReduce and DBMS Technologies for Analytical Workloads 2009
VLDB
0.00031099083
360
Efficient Parallel Set-Similarity Joins Using MapReduce 2010
SIGMOD
0.00020001237
561
Densest Subgraph in Streaming and MapReduce 2012
VLDB
0.00016390753
675
Hadoop++: Making a Yellow Elephant Run Like a Cheetah (Without It Even Noticing) 2010
VLDB
0.00014880686
754
Profiling, What-if Analysis, and Cost-based Optimization of MapReduce Programs 2011
VLDB
0.00014231311
799
A Comparison of Join Algorithms for Log Processing in MapReduce 2010
SIGMOD
0.00013882649
823
MRShare: Sharing Across Multiple Queries in MapReduce 2010
VLDB
0.00013642066
866
Processing Theta-Joins using MapReduce* 2011
SIGMOD
0.00013381756
876
Tenzing: A SQL Implementation On The MapReduce Framework 2011
VLDB
0.00013304112
964
Fast Personalized PageRank on MapReduce 2011
SIGMOD
0.00012814643
978
Parallel Evaluation of Conjunctive Queries 2011
PODS
0.00012725823
1,021
Online Aggregation for Large MapReduce Jobs 2011
VLDB
0.00012437619
1,037
Jaql: A Scripting Language for Large Scale Semistructured Data Analysis 2011
VLDB
0.00012371105
1,282
Automatic Optimization for MapReduce Programs 2011
VLDB
0.00011208192
1,351
SkewTune: Mitigating Skew in MapReduce Applications 2012
SIGMOD
0.00010929229
1,421
V-SMART-Join: A Scalable MapReduce Framework for All-Pair Similarity Joins of Multisets and Vectors 2012
VLDB
0.00010722146
1,688
ParaTimer: A Progress Indicator for MapReduce DAGs 2010
SIGMOD
9.860716e-05
1,708
PerfXplain: Debugging MapReduce Job Performance 2012
VLDB
9.8184303e-05
1,838
Cheetah: A High Performance, Custom Data Warehouse on Top of MapReduce 2010
VLDB
9.5305061e-05
1,925
ReStore: Reusing Results of MapReduce Jobs 2012
VLDB
9.3643089e-05
2,175
Efficient Processing of k Nearest Neighbor Joins using MapReduce 2012
VLDB
8.918268e-05
2,527
Stubby: A Transformation-based Optimizer for MapReduce Workflows 2012
VLDB
8.3386546e-05
2,605
PLANET: Massively Parallel Learning of Tree Ensembles with MapReduce 2009
VLDB
8.2273571e-05
2,688
CoHadoop: Flexible Data Placement and Its Exploitation in Hadoop 2011
VLDB
8.1262948e-05
2,899
Social Content Matching in MapReduce 2011
VLDB
7.8813089e-05
2,903
Column-Oriented Storage Techniques for MapReduce 2011
VLDB
7.877293e-05
2,932
Efficient Multi-way Theta-Join Processing Using MapReduce 2012
VLDB
7.8368679e-05
3,009
Llama: Leveraging Columnar Storage for Scalable Join Processing in the MapReduce Framework 2011
SIGMOD
7.7570485e-05
3,144
Early Accurate Results for Advanced Analytics on MapReduce 2012
VLDB
7.5947114e-05
3,158
Energy Management for MapReduce Clusters 2010
VLDB
7.5798726e-05
3,781
M3R: Increased Performance for In-Memory Hadoop Jobs 2012
VLDB
7.0223677e-05
4,142
Behavioral Simulations in MapReduce 2010
VLDB
6.780997e-05
5,653
Building Wavelet Histograms on Large Data in MapReduce 2012
VLDB
6.048773e-05
Semantically Similar Papers