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.00010784123
Overall Rank: 1,393 | 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,547	Upper and Lower Bounds on the Cost of a Map-Reduce Computation	2013	VLDB	0.00010268377
1,562	Titian: Data Provenance Support in Spark	2016	VLDB	0.00010192248
1,722	SMOKE: Fine-grained Lineage at Interactive Speed	2018	VLDB	9.781628e-05
1,776	Putting Lipstick on Pig: Enabling Database-style Workflow Provenance	2012	VLDB	9.6661217e-05
2,845	Fine-Grained, Secure and Efficient Data Provenance on Blockchain Systems	2019	VLDB	7.9277292e-05
3,732	RAMP: A System for Capturing and Tracing Provenance in MapReduce Workflows	2011	VLDB	7.0438962e-05
4,354	LIMA: Fine-grained Lineage Tracing and Reuse in Machine Learning Systems	2021	SIGMOD	6.6318545e-05
4,963	Explaining Outputs in Modern Data Analytics	2016	VLDB	6.3234324e-05
5,660	A Quest for Beauty and Wealth (or, Business Processes for Database Researchers)	2011	PODS	6.0306257e-05
7,230	Dataset Relationship Management	2019	CIDR	5.5636441e-05
7,252	Hypothetical Reasoning via Provenance Abstraction	2019	SIGMOD	5.5583413e-05
7,901	To Not Miss the Forest for the Trees - A Holistic Approach for Explaining Missing Answers over Nested Data	2021	SIGMOD	5.4136249e-05
8,293	Distributed Time-aware Provenance	2013	VLDB	5.3440772e-05
8,323	Fixed It For You: Protocol Repair Using Lineage Graphs	2019	CIDR	5.3394119e-05
9,379	Tracking Personal Data Use: Provenance And Trust	2015	CIDR	5.170668e-05
10,236	Privacy-Preserving Network Provenance	2017	VLDB	5.0432098e-05
12,206	Capturing and Querying Structural Provenance in Spark with Pebble	2019	SIGMOD	4.9605343e-05
12,263	Demonstration of Smoke: A Deep Breath of Data-Intensive Lineage Applications	2018	SIGMOD	4.9605343e-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.0010494385
31	Hive - A Warehousing Solution Over a Map-Reduce Framework	2009	VLDB	0.00049707539
76	Map-Reduce-Merge: Simplified Relational Data Processing on Large Clusters	2007	SIGMOD	0.00036932687
592	Lineage Tracing for General Data Warehouse Transformations	2001	VLDB	0.0001583562
949	Provenance and Scientific Workflows: Challenges and Opportunities	2008	SIGMOD	0.00012897365
1,556	Update Exchange with Mappings and Provenance	2007	VLDB	0.00010232016
1,621	Efficient Provenance Storage	2008	SIGMOD	0.00010039235
1,923	Efficient Lineage Tracking For Scientific Workflows	2008	SIGMOD	9.3550626e-05

Semantically Similar Papers

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