Provenance-based Data Skipping

Summary: Proposes provenance-based data skipping (PBDS) that builds compact provenance sketches encoding data relevance for a query, e.g., HAVING and top-k. These sketches speed up subsequent queries and can leverage physical design artifacts like indexes and zone maps. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12922
Venue: VLDB
Year: 2022
Pagerank: 4.4237386e-05
Overall Rank: 8,886 | 38.25%
DOI: 10.14778/3494124.3494130

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,410	Pruning in Snowflake: Working Smarter, Not Harder	2025	SIGMOD	4.5154358e-05
10,890	FaDE: More Than a Million What-ifs Per Second	2025	VLDB	4.1905499e-05
10,899	Towards an Objective Metric for Data Value Through Relevance	2024	CIDR	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 37 of 37 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
24	The R+-Tree: A Dynamic Index For Multi-Dimensional Objects	1987	VLDB	0.00083300888
31	Provenance Semirings	2007	PODS	0.00078516827
160	Automated Selection of Materialized Views and Indexes for SQL Databases	2000	VLDB	0.00040053897
213	Scorpion: Explaining Away Outliers in Aggregate Queries	2013	VLDB	0.0003371037
283	Integrating Vertical and Horizontal Partitioning into Automated Physical Database Design	2004	SIGMOD	0.00029024583
297	Complexity of Answering Queries Using Materialized Views	1998	PODS	0.00028572729
367	Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing	1998	VLDB	0.00025518228
561	An Annotation Management System for Relational Databases	2004	VLDB	0.00020099434
585	DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views	2012	VLDB	0.00019682634
728	Optimizing Queries Using Materialized Views: A Practical, Scalable Solution	2001	SIGMOD	0.00017459654
943	A Formal Approach to Finding Explanations for Database Queries	2014	SIGMOD	0.00015140995
1,096	Interpretable and Informative Explanations of Outcomes	2015	VLDB	0.00014088686
1,106	Provenance for Aggregate Queries	2011	PODS	0.00013976386
1,646	Caravan: Provisioning for What-If Analysis	2013	CIDR	0.00011026644
1,864	Efficient Provenance Storage	2008	SIGMOD	0.00010277171
1,988	A Practical Scalable Distributed B-Tree	2008	VLDB	9.8500023e-05
1,993	Column Imprints: A Secondary Index Structure	2013	SIGMOD	9.8403548e-05
2,259	ProvSQL: Provenance and Probability Management in PostgreSQL	2018	VLDB	9.1790333e-05
2,286	SMOKE: Fine-grained Lineage at Interactive Speed	2018	VLDB	9.102574e-05
2,361	Merging What’s Cracked, Cracking What’s Merged: Adaptive Indexing in Main-Memory Column-Stores	2011	VLDB	8.9648608e-05
2,655	Explaining Query Answers with Explanation-Ready Databases	2016	VLDB	8.3638668e-05
2,731	Vertical Partitioning for Database Design: A Graphical Algorithm	1989	SIGMOD	8.2141333e-05
2,770	The Semiring Framework for Database Provenance	2017	PODS	8.1495762e-05
3,160	Horizontal Data Partitioning In Database Design	1982	SIGMOD	7.4649653e-05
3,587	Efficient Querying and Maintenance of Network Provenance at Internet-Scale	2010	SIGMOD	6.9394966e-05
3,731	Skipping-oriented Partitioning for Columnar Layouts	2017	VLDB	6.8074069e-05
3,906	Two Birds, One Stone: A Fast, yet Lightweight, Indexing Scheme for Modern Database Systems	2017	VLDB	6.6413008e-05
4,363	Indexing on Modern Hardware: Hekaton and Beyond	2014	SIGMOD	6.2476591e-05
6,088	Distributed Provenance Compression	2017	SIGMOD	5.2146574e-05
6,700	Approximate Summaries for Why and Why-not Provenance	2020	VLDB	4.9534371e-05
6,777	Revisiting Reuse in Main Memory Database Systems	2017	SIGMOD	4.9242249e-05
7,208	Efficient Bulk Updates on Multiversion B-trees	2013	VLDB	4.795225e-05
7,713	Query Centric Partitioning and Allocation for Partially Replicated Database Systems	2017	SIGMOD	4.6662571e-05
8,228	You Say 'What', I Hear 'Where' and 'Why' - (Mis-)Interpreting SQL to Derive Fine-Grained Provenance	2018	VLDB	4.549777e-05
8,392	Hypothetical Reasoning via Provenance Abstraction	2019	SIGMOD	4.5234647e-05
9,906	PROPOLIS: Provisioned Analysis of Data-Centric Processes	2013	VLDB	4.2536369e-05
11,740	Provenance Summaries for Answers and Non-Answers	2018	VLDB	4.1905499e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,031	Provenance for SQL through Abstract Interpretation: Value-less, but Worthwhile	2015	VLDB	4.3998298e-05
10,555	Evaluating Continuous Queries with Inconsistency Annotations	2025	VLDB	4.1905499e-05
12,001	A Partitioning Framework for Aggressive Data Skipping	2014	VLDB	4.1905499e-05
6,807	Adaptive Data Skipping in Main-Memory Systems	2016	SIGMOD	4.915939e-05
8,725	OneProvenance: Efficient Extraction of Dynamic Coarse-Grained Provenance From Database Query Event Logs	2023	VLDB	4.453957e-05
8,392	Hypothetical Reasoning via Provenance Abstraction	2019	SIGMOD	4.5234647e-05
6,187	On Provenance Minimization	2011	PODS	5.1611195e-05
2,182	Querying Data Provenance	2010	SIGMOD	9.3596252e-05
6,461	Pando: Enhanced Data Skipping with Logical Data Partitioning	2023	VLDB	5.0479786e-05
3,923	Pushing Data-Induced Predicates Through Joins in Big-Data Clusters	2020	VLDB	6.6232068e-05