Provenance for Generalized Map and Reduce Workflows

Summary: Proposes a formal provenance model for generalized map-and-reduce workflows (acyclic DAGs of map/reduce), enabling recursive composition and both backward and forward tracing between inputs and outputs. Implements transparent, wrapper-based capture in Hadoop that preserves parallelism and fault-tolerance and reports prototype performance. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h6486d7ffcf1491e5
Venue: CIDR
Year: 2011
Pagerank: 0.00010818511
Overall Rank: 1,389 | 90.67%
DOI: -
PDF: Download (CC BY 3.0)

Incoming Non-self Citations Over Time

Authors

1. Robert Ikeda (Stanford University)
2. Hyunjung Park (Stanford University)
3. Jennifer Widom (Stanford University)

BibTeX Citation

@inproceedings{ikeda_cidr11,
        address = {Amsterdam, Netherlands},
        series = {{CIDR} '11},
        title = {{Provenance for Generalized Map and Reduce Workflows}},
        booktitle = {Proceedings of the {Conference} on {Innovative} {Data} {Systems} {Research}},
        author = {Ikeda, Robert and Park, Hyunjung and Widom, Jennifer},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 18 of 18 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,546	Upper and Lower Bounds on the Cost of a Map-Reduce Computation	2013	VLDB	0.0001029751
1,564	Titian: Data Provenance Support in Spark	2016	VLDB	0.00010219222
1,713	SMOKE: Fine-grained Lineage at Interactive Speed	2018	VLDB	9.8129981e-05
1,767	Putting Lipstick on Pig: Enabling Database-style Workflow Provenance	2012	VLDB	9.6910812e-05
2,835	Fine-Grained, Secure and Efficient Data Provenance on Blockchain Systems	2019	VLDB	7.9516187e-05
3,727	RAMP: A System for Capturing and Tracing Provenance in MapReduce Workflows	2011	VLDB	7.0668631e-05
4,334	LIMA: Fine-grained Lineage Tracing and Reuse in Machine Learning Systems	2021	SIGMOD	6.6537801e-05
4,937	Explaining Outputs in Modern Data Analytics	2016	VLDB	6.3443901e-05
5,646	A Quest for Beauty and Wealth (or, Business Processes for Database Researchers)	2011	PODS	6.0505202e-05
7,210	Dataset Relationship Management	2019	CIDR	5.5821013e-05
7,235	Hypothetical Reasoning via Provenance Abstraction	2019	SIGMOD	5.5765963e-05
7,884	To Not Miss the Forest for the Trees - A Holistic Approach for Explaining Missing Answers over Nested Data	2021	SIGMOD	5.4315851e-05
8,277	Distributed Time-aware Provenance	2013	VLDB	5.3618022e-05
8,309	Fixed It For You: Protocol Repair Using Lineage Graphs	2019	CIDR	5.3571259e-05
9,353	Tracking Personal Data Use: Provenance And Trust	2015	CIDR	5.1878222e-05
10,203	Privacy-Preserving Network Provenance	2017	VLDB	5.0599411e-05
12,163	Capturing and Querying Structural Provenance in Spark with Pebble	2019	SIGMOD	4.9769913e-05
12,220	Demonstration of Smoke: A Deep Breath of Data-Intensive Lineage Applications	2018	SIGMOD	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 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
31	Hive - A Warehousing Solution Over a Map-Reduce Framework	2009	VLDB	0.00049821554
75	Map-Reduce-Merge: Simplified Relational Data Processing on Large Clusters	2007	SIGMOD	0.0003702496
590	Lineage Tracing for General Data Warehouse Transformations	2001	VLDB	0.00015884721
943	Provenance and Scientific Workflows: Challenges and Opportunities	2008	SIGMOD	0.00012939577
1,554	Update Exchange with Mappings and Provenance	2007	VLDB	0.00010265583
1,611	Efficient Provenance Storage	2008	SIGMOD	0.00010072076
1,914	Efficient Lineage Tracking For Scientific Workflows	2008	SIGMOD	9.3845472e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,767	Putting Lipstick on Pig: Enabling Database-style Workflow Provenance	2012	VLDB
2	12,166	Ursprung: Provenance for Large-Scale Analytics Environments	2019	SIGMOD
3	7,366	Enabling Privacy in Provenance-Aware Workflow Systems	2011	CIDR
4	8,277	Distributed Time-aware Provenance	2013	VLDB
5	6,442	Tracing Lineage Beyond Relational Operators	2007	VLDB
6	10,838	Toward Temporal Attribution Analytics in Dataflows	2026	VLDB
7	590	Lineage Tracing for General Data Warehouse Transformations	2001	VLDB
8	7,214	Capturing and Querying Fine-grained Provenance of Preprocessing Pipelines in Data Science	2021	VLDB
9	1,914	Efficient Lineage Tracking For Scientific Workflows	2008	SIGMOD
10	3,727	RAMP: A System for Capturing and Tracing Provenance in MapReduce Workflows	2011	VLDB