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: 170
Venue: CIDR
Year: 2011
Pagerank: 0.00011016972
Overall Rank: 1,366 | 90.63%
DOI: -

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,514	Upper and Lower Bounds on the Cost of a Map-Reduce Computation	2013	VLDB	0.00010527649
1,617	Titian: Data Provenance Support in Spark	2016	VLDB	0.00010209397
1,786	Putting Lipstick on Pig: Enabling Database-style Workflow Provenance	2012	VLDB	9.7690421e-05
1,798	SMOKE: Fine-grained Lineage at Interactive Speed	2018	VLDB	9.7361937e-05
2,851	Fine-Grained, Secure and Efficient Data Provenance on Blockchain Systems	2019	VLDB	8.0462369e-05
3,675	RAMP: A System for Capturing and Tracing Provenance in MapReduce Workflows	2011	VLDB	7.2096638e-05
4,240	LIMA: Fine-grained Lineage Tracing and Reuse in Machine Learning Systems	2021	SIGMOD	6.809685e-05
4,845	Explaining Outputs in Modern Data Analytics	2016	VLDB	6.4818607e-05
5,511	A Quest for Beauty and Wealth (or, Business Processes for Database Researchers)	2011	PODS	6.1915384e-05
7,065	Dataset Relationship Management	2019	CIDR	5.7123431e-05
7,748	To Not Miss the Forest for the Trees - A Holistic Approach for Explaining Missing Answers over Nested Data	2021	SIGMOD	5.5528084e-05
8,171	Fixed It For You: Protocol Repair Using Lineage Graphs	2019	CIDR	5.4740088e-05
8,509	Hypothetical Reasoning via Provenance Abstraction	2019	SIGMOD	5.4120069e-05
8,610	Distributed Time-aware Provenance	2013	VLDB	5.4022415e-05
9,208	Tracking Personal Data Use: Provenance And Trust	2015	CIDR	5.3058708e-05
11,857	Capturing and Querying Structural Provenance in Spark with Pebble	2019	SIGMOD	5.093636e-05
11,915	Demonstration of Smoke: A Deep Breath of Data-Intensive Lineage Applications	2018	SIGMOD	5.093636e-05
12,002	Privacy-Preserving Network Provenance	2017	VLDB	5.093636e-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.0010686205
32	Hive - A Warehousing Solution Over a Map-Reduce Framework	2009	VLDB	0.00050111008
72	Map-Reduce-Merge: Simplified Relational Data Processing on Large Clusters	2007	SIGMOD	0.00037695852
585	Lineage Tracing for General Data Warehouse Transformations	2001	VLDB	0.00016139897
919	Provenance and Scientific Workflows: Challenges and Opportunities	2008	SIGMOD	0.00013214041
1,599	Update Exchange with Mappings and Provenance	2007	VLDB	0.00010241307
1,627	Efficient Provenance Storage	2008	SIGMOD	0.00010188097
1,871	Efficient Lineage Tracking For Scientific Workflows	2008	SIGMOD	9.5783449e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	919	Provenance and Scientific Workflows: Challenges and Opportunities	2008	SIGMOD
2	1,786	Putting Lipstick on Pig: Enabling Database-style Workflow Provenance	2012	VLDB
3	11,860	Ursprung: Provenance for Large-Scale Analytics Environments	2019	SIGMOD
4	7,215	Enabling Privacy in Provenance-Aware Workflow Systems	2011	CIDR
5	8,610	Distributed Time-aware Provenance	2013	VLDB
6	6,351	Tracing Lineage Beyond Relational Operators	2007	VLDB
7	585	Lineage Tracing for General Data Warehouse Transformations	2001	VLDB
8	8,050	Capturing and Querying Fine-grained Provenance of Preprocessing Pipelines in Data Science	2021	VLDB
9	1,871	Efficient Lineage Tracking For Scientific Workflows	2008	SIGMOD
10	3,675	RAMP: A System for Capturing and Tracing Provenance in MapReduce Workflows	2011	VLDB