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.00010821908
Overall Rank: 1,388 | 90.67%
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,545	Upper and Lower Bounds on the Cost of a Map-Reduce Computation	2013	VLDB	0.00010302384
1,564	Titian: Data Provenance Support in Spark	2016	VLDB	0.00010222394
1,746	SMOKE: Fine-grained Lineage at Interactive Speed	2018	VLDB	9.7341914e-05
1,765	Putting Lipstick on Pig: Enabling Database-style Workflow Provenance	2012	VLDB	9.6955585e-05
2,835	Fine-Grained, Secure and Efficient Data Provenance on Blockchain Systems	2019	VLDB	7.9553846e-05
3,725	RAMP: A System for Capturing and Tracing Provenance in MapReduce Workflows	2011	VLDB	7.0702061e-05
4,334	LIMA: Fine-grained Lineage Tracing and Reuse in Machine Learning Systems	2021	SIGMOD	6.6569314e-05
4,940	Explaining Outputs in Modern Data Analytics	2016	VLDB	6.345789e-05
5,644	A Quest for Beauty and Wealth (or, Business Processes for Database Researchers)	2011	PODS	6.0533802e-05
7,208	Dataset Relationship Management	2019	CIDR	5.584745e-05
7,234	Hypothetical Reasoning via Provenance Abstraction	2019	SIGMOD	5.5792063e-05
7,879	To Not Miss the Forest for the Trees - A Holistic Approach for Explaining Missing Answers over Nested Data	2021	SIGMOD	5.4341576e-05
8,273	Distributed Time-aware Provenance	2013	VLDB	5.3642993e-05
8,302	Fixed It For You: Protocol Repair Using Lineage Graphs	2019	CIDR	5.3596631e-05
9,344	Tracking Personal Data Use: Provenance And Trust	2015	CIDR	5.1902792e-05
10,197	Privacy-Preserving Network Provenance	2017	VLDB	5.0623376e-05
12,157	Capturing and Querying Structural Provenance in Spark with Pebble	2019	SIGMOD	4.9793485e-05
12,214	Demonstration of Smoke: A Deep Breath of Data-Intensive Lineage Applications	2018	SIGMOD	4.9793485e-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.001052036
31	Hive - A Warehousing Solution Over a Map-Reduce Framework	2009	VLDB	0.00049839909
75	Map-Reduce-Merge: Simplified Relational Data Processing on Large Clusters	2007	SIGMOD	0.0003704106
591	Lineage Tracing for General Data Warehouse Transformations	2001	VLDB	0.00015888097
943	Provenance and Scientific Workflows: Challenges and Opportunities	2008	SIGMOD	0.00012945546
1,555	Update Exchange with Mappings and Provenance	2007	VLDB	0.00010269848
1,610	Efficient Provenance Storage	2008	SIGMOD	0.00010076616
1,913	Efficient Lineage Tracking For Scientific Workflows	2008	SIGMOD	9.3887234e-05

Semantically Similar Papers

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