ParaTimer: A Progress Indicator for MapReduce DAGs

Summary: ParaTimer is a DAG-aware progress estimator for MapReduce workflows, using critical-path analysis to predict remaining time across paths. It handles failures and skew with multiple scenario estimates; implemented in Pig and validated on a cluster. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h2d1ce0a579a23c70
Venue: SIGMOD
Year: 2010
Pagerank: 9.8645784e-05
Overall Rank: 1,688 | 88.66%
DOI: 10.1145/1807167.1807223

Incoming Non-self Citations Over Time

Authors

1. Kristi Morton (University of Washington)
2. Magdalena Balazinska (University of Washington)
3. Dan Grossman (University of Washington)

BibTeX Citation

@inproceedings{morton_sigmod10,
        title = {{ParaTimer: A Progress Indicator for MapReduce DAGs}},
        author = {Morton, Kristi and Balazinska, Magdalena and Grossman, Dan},
        series = {{SIGMOD} '10},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1807167.1807223},
        url = {https://dl.acm.org/doi/10.1145/1807167.1807223},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
560	Plan-Structured Deep Neural Network Models for Query Performance Prediction	2019	VLDB	0.00016403151
629	Performance Prediction for Concurrent Database Workloads	2011	SIGMOD	0.00015429949
1,072	Interactive Analytical Processing in Big Data Systems: A Cross-Industry Study of MapReduce Workloads	2012	VLDB	0.00012168947
1,708	PerfXplain: Debugging MapReduce Job Performance	2012	VLDB	9.8224587e-05
2,282	A Platform for Scalable One-Pass Analytics using MapReduce	2011	SIGMOD	8.6964781e-05
2,573	Minimal MapReduce Algorithms	2013	SIGMOD	8.2821647e-05
4,116	Resource Elasticity for Large-Scale Machine Learning	2015	SIGMOD	6.7961306e-05
5,386	PREDIcT: Towards Predicting the Runtime of Large Scale Iterative Analytics	2013	VLDB	6.1522468e-05
6,241	Operator and Query Progress Estimation in Microsoft SQL Server Live Query Statistics	2016	SIGMOD	5.8381762e-05
6,435	MIFO: A Query-Semantic Aware Resource Allocation Policy	2019	SIGMOD	5.7859508e-05
6,456	A Statistical Approach Towards Robust Progress Estimation	2012	VLDB	5.7782179e-05
7,967	Resource Bricolage for Parallel Database Systems	2015	VLDB	5.415894e-05
8,825	Toward Progress Indicators on Steroids for Big Data Systems	2013	CIDR	5.268646e-05
9,816	Supporting Scalable Analytics with Latency Constraints	2015	VLDB	5.1257999e-05
12,439	Big Data Research: Will Industry Solve all the Problems?	2015	VLDB	4.9793485e-05
12,548	Workload Management for Big Data Analytics	2013	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 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.001052036
9	Online Aggregation	1997	SIGMOD	0.00076195956
1,159	Toward a Progress Indicator for Database Queries	2004	SIGMOD	0.00011771949
1,587	Estimating Progress of Execution for SQL Queries	2004	SIGMOD	0.0001014156
2,318	When Can We Trust Progress Estimators for SQL Queries?	2005	SIGMOD	8.6464837e-05
2,978	Clustera: An Integrated Computation And Data Management System	2008	VLDB	7.7894665e-05
4,217	A Disk-Based Join With Probabilistic Guarantees*	2005	SIGMOD	6.7271293e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	43	A Comparison of Approaches to Large-Scale Data Analysis	2009	SIGMOD
2	12,375	Parallel Evaluation of Multi-Semi-Joins	2016	VLDB
3	2,318	When Can We Trust Progress Estimators for SQL Queries?	2005	SIGMOD
4	1,159	Toward a Progress Indicator for Database Queries	2004	SIGMOD
5	2,573	Minimal MapReduce Algorithms	2013	SIGMOD
6	977	Parallel Evaluation of Conjunctive Queries	2011	PODS
7	1,587	Estimating Progress of Execution for SQL Queries	2004	SIGMOD
8	9,773	Cost-based Fault-tolerance for Parallel Data Processing	2015	SIGMOD
9	8,825	Toward Progress Indicators on Steroids for Big Data Systems	2013	CIDR
10	8,474	ParTime: Parallel Temporal Aggregation	2016	SIGMOD