Relational Confidence Bounds Are Easy With The Bootstrap*

Summary: Proposes a plug-in bootstrap to compute confidence bounds for relational queries over sampled or incomplete data. Easy for DB programmers, broadly applicable, and ready to be integrated into analytic DBMS to provide probabilistic guarantees for AQP. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: ha3da2c21dc7a80cf
Venue: SIGMOD
Year: 2005
Pagerank: 8.1461074e-05
Overall Rank: 2,677 | 82.01%
DOI: 10.1145/1066157.1066224

Incoming Non-self Citations Over Time

Authors

1. Abhijit Pol (University of Florida)
2. Christopher Jermaine (University of Florida)

BibTeX Citation

@inproceedings{pol_sigmod05,
        title = {{Relational Confidence Bounds Are Easy With The Bootstrap*}},
        author = {Pol, Abhijit and Jermaine, Christopher},
        series = {{SIGMOD} '05},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1066157.1066224},
        url = {https://dl.acm.org/doi/10.1145/1066157.1066224},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
784	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.00014012614
1,428	Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems	2014	SIGMOD	0.00010693831
1,916	The Analytical Bootstrap: a New Method for Fast Error Estimation in Approximate Query Processing	2014	SIGMOD	9.3837729e-05
2,027	Database Learning: Toward a Database that Becomes Smarter Every Time	2017	SIGMOD	9.1618139e-05
2,224	DAQ: A New Paradigm for Approximate Query Processing	2015	VLDB	8.80823e-05
3,145	Early Accurate Results for Advanced Analytics on MapReduce	2012	VLDB	7.5965257e-05
3,424	AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics	2018	SIGMOD	7.3117029e-05
5,473	ABS: a System for Scalable Approximate Queries with Accuracy Guarantees	2014	SIGMOD	6.1178467e-05
6,227	iOLAP: Managing Uncertainty for Efficient Incremental OLAP	2016	SIGMOD	5.8452386e-05
7,978	Biathlon: Harnessing Model Resilience for Accelerating ML Inference Pipelines	2024	VLDB	5.4136835e-05
8,223	PilotDB: Database-Agnostic Online Approximate Query Processing with A Priori Error Guarantees	2025	SIGMOD	5.3751366e-05
9,764	Sapprox: Enabling Efficient and Accurate Approximations on Sub-datasets with Distribution-aware Online Sampling	2017	VLDB	5.1344728e-05
10,402	Accelerating Approximate Analytical Join Queries over Unstructured Data with Statistical Guarantees	2026	SIGMOD	4.9793485e-05
12,215	Demonstration of VerdictDB, the Platform-Independent AQP System	2018	SIGMOD	4.9793485e-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
9	Online Aggregation	1997	SIGMOD	0.00076195956
77	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00036828234
79	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00036487763
135	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00029866033
295	Towards Estimation Error Guarantees for Distinct Values	2000	PODS	0.00021914399
336	The Aqua Approximate Query Answering System	1999	SIGMOD	0.00020657819
1,203	Fixed-Precision Estimation of Join Selectivity	1993	PODS	0.00011548537

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,904	Estimating the Confidence of Conditional Functional Dependencies	2009	SIGMOD
2	1,428	Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems	2014	SIGMOD
3	79	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD
4	5,473	ABS: a System for Scalable Approximate Queries with Accuracy Guarantees	2014	SIGMOD
5	6,456	A Statistical Approach Towards Robust Progress Estimation	2012	VLDB
6	1,429	Top-down statistical estimation on a database	1983	SIGMOD
7	492	Error-Constrained COUNT Query Evaluation in Relational Databases	1991	SIGMOD
8	569	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD
9	58	Statistical Estimators for Relational Algebra Expressions	1988	PODS
10	1,916	The Analytical Bootstrap: a New Method for Fast Error Estimation in Approximate Query Processing	2014	SIGMOD