Efficient Provenance Storage

Summary: Proposes efficient provenance storage via three techniques—factorization and two inheritance-based methods—to reduce provenance data while preserving queryability. Applied to MiMI, Karma, and PReServ, it yields up to 20x storage reduction with efficient queries and cheap incremental updates. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h8ff2efadca59f113
Venue: SIGMOD
Year: 2008
Pagerank: 0.00010039235
Overall Rank: 1,621 | 89.14%
DOI: 10.1145/1376616.1376715

Incoming Non-self Citations Over Time

Authors

1. Adriane P. Chapman (University of Michigan)
2. H.V. Jagadish (University of Michigan)
3. Prakash Ramanan (Wichita State University)

BibTeX Citation

@inproceedings{chapman_sigmod08,
        title = {{Efficient Provenance Storage}},
        author = {Chapman, Adriane P. and Jagadish, H.V. and Ramanan, Prakash},
        series = {{SIGMOD} '08},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1376616.1376715},
        url = {https://dl.acm.org/doi/10.1145/1376616.1376715},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 19 of 19 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,393	Provenance for Generalized Map and Reduce Workflows	2011	CIDR	0.00010784123
1,837	Querying Data Provenance	2010	SIGMOD	9.5210079e-05
4,697	Provenance for Natural Language Queries	2017	VLDB	6.4479645e-05
5,556	Putting Things into Context: Rich Explanations for Query Answers using Join Graphs	2021	SIGMOD	6.0705311e-05
5,641	Distributed Provenance Compression	2017	SIGMOD	6.0377578e-05
5,748	An Optimal Labeling Scheme for Workflow Provenance Using Skeleton Labels	2010	SIGMOD	5.9914851e-05
6,472	On Provenance Minimization	2011	PODS	5.7561073e-05
6,502	Approximate Summaries for Why and Why-not Provenance	2020	VLDB	5.7468661e-05
6,728	Selective Provenance for Datalog Programs Using Top-K Queries	2015	VLDB	5.6812425e-05
7,252	Hypothetical Reasoning via Provenance Abstraction	2019	SIGMOD	5.5583413e-05
7,575	Detecting and Resolving Unsound Workflow Views for Correct Provenance Analysis	2009	SIGMOD	5.4768074e-05
8,101	Provenance-Enabled Explainable AI	2024	SIGMOD	5.3739121e-05
8,505	Provenance-based Data Skipping	2022	VLDB	5.3126038e-05
8,967	Compact, Tamper-Resistant Archival of Fine-Grained Provenance	2021	VLDB	5.2356443e-05
9,630	Equivalence-Invariant Algebraic Provenance for Hyperplane Update Queries	2020	SIGMOD	5.1363807e-05
9,980	NLProv: Natural Language Provenance	2016	VLDB	5.0870037e-05
10,899	Toward Temporal Attribution Analytics in Dataflows	2026	VLDB	4.9605343e-05
11,203	Unified Lineage System: Tracking Data Provenance at Scale	2025	SIGMOD	4.9605343e-05
12,007	Flow Provenance in Temporal Interaction Networks	2021	SIGMOD	4.9605343e-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
85	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00035848027
529	An Annotation Management System for Relational Databases	2004	VLDB	0.00016834919
592	Lineage Tracing for General Data Warehouse Transformations	2001	VLDB	0.0001583562
715	Archiving Scientific Data	2002	SIGMOD	0.00014558752
1,018	XMill: an Efficient Compressor for XML Data	2000	SIGMOD	0.00012451992
2,186	Provenance Management in Curated Databases	2006	SIGMOD	8.8910881e-05
5,326	The Virtual Data Grid: A New Model and Architecture for Data-Intensive Collaboration	2003	CIDR	6.1642681e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,641	Distributed Provenance Compression	2017	SIGMOD
2	6,502	Approximate Summaries for Why and Why-not Provenance	2020	VLDB
3	2,847	Data Provenance at Internet Scale: Architecture, Experiences, and the Road Ahead	2017	CIDR
4	1,837	Querying Data Provenance	2010	SIGMOD
5	7,252	Hypothetical Reasoning via Provenance Abstraction	2019	SIGMOD
6	8,967	Compact, Tamper-Resistant Archival of Fine-Grained Provenance	2021	VLDB
7	12,025	On Optimizing the Trade-off between Privacy and Utility in Data Provenance	2021	SIGMOD
8	1,923	Efficient Lineage Tracking For Scientific Workflows	2008	SIGMOD
9	6,472	On Provenance Minimization	2011	PODS
10	2,186	Provenance Management in Curated Databases	2006	SIGMOD