Database Paper Browser

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
4653
Venue
SIGMOD
Year
2013
Pagerank
8.2426646e-05
Overall Rank
2,714 | 81.14%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank Citing Paper Year Venue Pagerank
2,172 Scalable Subgraph Enumeration in MapReduce 2015 VLDB 9.37776e-05
2,916 Pregel Algorithms for Graph Connectivity Problems with Performance Guarantees 2014 VLDB 7.9062736e-05
3,188 Scalable Big Graph Processing in MapReduce 2014 SIGMOD 7.4142307e-05
3,478 Functional Dependencies for Graphs 2016 SIGMOD 7.0554625e-05
5,954 A Tight Lower Bound for Comparison-Based Quantile Summaries 2020 PODS 5.2542261e-05
6,119 Distributed Graph Simulation: Impossibility and Possibility 2014 VLDB 5.1991813e-05
7,046 Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability 2018 VLDB 4.8471584e-05
7,410 On Scale Independence for Querying Big Data 2014 PODS 4.7320027e-05
11,439 Algorithms for a Topology-aware Massively Parallel Computation Model 2021 PODS 4.1905499e-05
11,843 An Efficient MapReduce Cube Algorithm for Varied Data Distributions 2016 SIGMOD 4.1905499e-05
11,890 Parallel Evaluation of Multi-Semi-Joins 2016 VLDB 4.1905499e-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.

Rank Cited Paper Year Venue Pagerank
3 Pig Latin: A Not-So-Foreign Language for Data Processing 2008 SIGMOD 0.0024217964
22 SCOPE: Easy and Efficient Parallel Processing of Massive Data Sets 2008 VLDB 0.00084679526
109 Dremel: Interactive Analysis of Web-Scale Datasets 2010 VLDB 0.00048217028
158 HadoopDB: An Architectural Hybrid of MapReduce and DBMS Technologies for Analytical Workloads 2009 VLDB 0.00040401371
442 Efficient Parallel Set-Similarity Joins Using MapReduce 2010 SIGMOD 0.00023095823
645 Densest Subgraph in Streaming and MapReduce 2012 VLDB 0.00018727714
789 Hadoop++: Making a Yellow Elephant Run Like a Cheetah (Without It Even Noticing) 2010 VLDB 0.00016602215
866 Profiling, What-if Analysis, and Cost-based Optimization of MapReduce Programs 2011 VLDB 0.00015771189
875 Fast Personalized PageRank on MapReduce 2011 SIGMOD 0.00015679931
909 Tenzing A SQL Implementation On The MapReduce Framework 2011 VLDB 0.0001540191
947 MRShare: Sharing Across Multiple Queries in MapReduce 2010 VLDB 0.00015112344
962 A Comparison of Join Algorithms for Log Processing in MapReduce 2010 SIGMOD 0.00015003834
1,073 Processing Theta-Joins using MapReduce* 2011 SIGMOD 0.00014255717
1,114 Parallel Evaluation of Conjunctive Queries 2011 PODS 0.00013871948
1,265 Jaql: A Scripting Language for Large Scale Semistructured Data Analysis 2011 VLDB 0.00012933537
1,281 Automatic Optimization for MapReduce Programs 2011 VLDB 0.00012837411
1,339 SkewTune: Mitigating Skew in MapReduce Applications 2012 SIGMOD 0.00012492978
1,451 Online Aggregation for Large MapReduce Jobs 2011 VLDB 0.00011925842
1,533 PerfXplain: Debugging MapReduce Job Performance 2012 VLDB 0.00011462982
1,768 ParaTimer: A Progress Indicator for MapReduce DAGs 2010 SIGMOD 0.00010608933
1,775 V-SMART-Join: A Scalable MapReduce Framework for All-Pair Similarity Joins of Multisets and Vectors 2012 VLDB 0.00010584816
1,888 Social Content Matching in MapReduce 2011 VLDB 0.00010196528
1,927 Efficient Processing of k Nearest Neighbor Joins using MapReduce 2012 VLDB 0.00010062395
1,945 Cheetah: A High Performance, Custom Data Warehouse on Top of MapReduce 2010 VLDB 0.0001000706
2,211 ReStore: Reusing Results of MapReduce Jobs 2012 VLDB 9.2823037e-05
2,441 CoHadoop: Flexible Data Placement and Its Exploitation in Hadoop 2011 VLDB 8.8106295e-05
2,636 PLANET: Massively Parallel Learning of Tree Ensembles with MapReduce 2009 VLDB 8.401513e-05
2,754 Stubby: A Transformation-based Optimizer for MapReduce Workflows 2012 VLDB 8.1720428e-05
3,068 Efficient Multi-way Theta-Join Processing Using MapReduce 2012 VLDB 7.6241861e-05
3,120 Llama: Leveraging Columnar Storage for Scalable Join Processing in the MapReduce Framework 2011 SIGMOD 7.533894e-05
3,186 Energy Management for MapReduce Clusters 2010 VLDB 7.4218249e-05
3,193 Column-Oriented Storage Techniques for MapReduce 2011 VLDB 7.4073719e-05
3,247 Early Accurate Results for Advanced Analytics on MapReduce 2012 VLDB 7.3237519e-05
3,511 M3R: Increased Performance for In-Memory Hadoop Jobs 2012 VLDB 7.0242945e-05
3,633 Behavioral Simulations in MapReduce 2010 VLDB 6.8959345e-05
5,908 Building Wavelet Histograms on Large Data in MapReduce 2012 VLDB 5.2731311e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
4,752 Set Similarity Joins on MapReduce: An Experimental Survey 2018 VLDB 5.9396804e-05
866 Profiling, What-if Analysis, and Cost-based Optimization of MapReduce Programs 2011 VLDB 0.00015771189
1,451 Online Aggregation for Large MapReduce Jobs 2011 VLDB 0.00011925842
3,188 Scalable Big Graph Processing in MapReduce 2014 SIGMOD 7.4142307e-05
1,312 Upper and Lower Bounds on the Cost of a Map-Reduce Computation 2013 VLDB 0.00012650678
2,476 A Platform for Scalable One-Pass Analytics using MapReduce 2011 SIGMOD 8.6907971e-05
15 Map-Reduce-Merge: Simplified Relational Data Processing on Large Clusters 2007 SIGMOD 0.0010668335
1,615 The Performance of MapReduce: An In-depth Study 2010 VLDB 0.00011137225
42 A Comparison of Approaches to Large-Scale Data Analysis 2009 SIGMOD 0.00073570328
3,709 Multi-Query Optimization in MapReduce Framework 2014 VLDB 6.8211506e-05