Approximate Selection with Guarantees using Proxies

Summary: Introduces algorithms for approximate selection with statistical guarantees using cheap proxies and limited exact identifications from an oracle. Guarantees target precision or recall with high probability, outperforming prior proxy-based methods—up to 30x improvement on real and synthetic datasets. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12282
Venue: VLDB
Year: 2020
Pagerank: 7.978725e-05
Overall Rank: 2,898 | 80.12%
DOI: 10.14778/3407790.3407804

Incoming Non-self Citations Over Time

Authors

1. Daniel Kang (Stanford University)
2. Edward Gan (Stanford University)
3. Peter Bailis (Stanford University)
4. Tatsunori Hashimoto (Stanford University)
5. Matei Zaharia (Stanford University)

BibTeX Citation

@article{kang_vldb20,
        title = {{Approximate Selection with Guarantees using Proxies}},
        author = {Kang, Daniel and Gan, Edward and Bailis, Peter and Hashimoto, Tatsunori and Zaharia, Matei},
        journal = {PVLDB},
        series = {{VLDB} '20},
        volume = {13},
        number = {11},
        pages = {1990--2003},
        doi = {10.14778/3407790.3407804},
        url = {https://doi.org/10.14778/3407790.3407804},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 23 of 23 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,253	Jointly Optimizing Preprocessing and Inference for DNN-based Visual Analytics	2021	VLDB	7.5936939e-05
3,766	TASTI: Semantic Indexes for Machine Learning-based Queries over Unstructured Data	2022	SIGMOD	7.1430942e-05
3,907	Accelerating Approximate Aggregation Queries with Expensive Predicates	2021	VLDB	7.0278233e-05
4,007	Optimizing Video Analytics with Declarative Model Relationships	2023	VLDB	6.9632395e-05
4,114	Optimizing Machine Learning Inference Queries with Correlative Proxy Models	2022	VLDB	6.8941194e-05
4,256	VIVA: An End-to-End System for Interactive Video Analytics	2022	CIDR	6.8018439e-05
5,789	Seiden: Revisiting Query Processing in Video Database Systems	2023	VLDB	6.0874367e-05
7,066	Aero: Adaptive Query Processing of ML Queries	2025	SIGMOD	5.712204e-05
7,568	Semantic Operators and Their Optimization: Enabling LLM-Based Data Processing with Accuracy Guarantees in LOTUS	2025	VLDB	5.5953379e-05
7,648	Accelerating Aggregation Queries on Unstructured Streams of Data	2023	VLDB	5.575838e-05
8,829	Cut Costs, Not Accuracy: LLM-Powered Data Processing with Guarantees	2026	SIGMOD	5.3613784e-05
9,353	On Efficient Approximate Queries over Machine Learning Models	2023	VLDB	5.2829539e-05
9,882	Demonstration of Accelerating Machine Learning Inference Queries with Correlative Proxy Models	2022	VLDB	5.2040783e-05
9,924	TVM: A Tile-based Video Management Framework	2024	VLDB	5.1955087e-05
9,927	Everest: A Top-K Deep Video Analytics System	2022	SIGMOD	5.1955087e-05
9,940	RALF: Accuracy-Aware Scheduling for Feature Store Maintenance	2024	VLDB	5.1924403e-05
10,186	Accelerating Approximate Analytical Join Queries over Unstructured Data with Statistical Guarantees	2026	SIGMOD	5.093636e-05
10,286	ScaleDoc: Scaling LLM-based Predicates over Large Document Collections	2026	SIGMOD	5.093636e-05
10,476	On Efficient Approximate Aggregate Nearest Neighbor Queries over Learned Representations	2026	SIGMOD	5.093636e-05
10,504	Task Cascades for Efficient Unstructured Data Processing	2026	SIGMOD	5.093636e-05
10,670	MAST: Towards Efficient Analytical Query Processing on Point Cloud Data	2025	SIGMOD	5.093636e-05
10,795	Scalable Complex Event Processing on Video Streams	2025	SIGMOD	5.093636e-05
11,624	Accelerating Queries over Unstructured Data with ML	2021	CIDR	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 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.00077458002
75	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00037277061
131	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00030424509
132	Predicate Migration: Optimizing Queries with Expensive Predicates	1993	SIGMOD	0.00030378624
255	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00023174541
284	NoScope: Optimizing Neural Network Queries over Video at Scale	2017	VLDB	0.00022370521
288	Towards Estimation Error Guarantees for Distinct Values	2000	PODS	0.00022296371
295	Accelerating Machine Learning Inference with Probabilistic Predicates	2018	SIGMOD	0.00022238183
307	Approximate Query Processing Using Wavelets	2000	VLDB	0.00021792475
451	Mergeable Summaries	2012	PODS	0.00018151445
569	BlazeIt: Optimizing Declarative Aggregation and Limit Queries for Neural Network-Based Video Analytics	2020	VLDB	0.00016348191
827	Minimal Probing: Supporting Expensive Predicates for Top-k Queries	2002	SIGMOD	0.00013769938
1,401	Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems	2014	SIGMOD	0.00010889902
2,747	Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries	2018	VLDB	8.1711208e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,114	Optimizing Machine Learning Inference Queries with Correlative Proxy Models	2022	VLDB
2	8,124	Consistent and Flexible Selectivity Estimation for High-Dimensional Data	2021	SIGMOD
3	8,589	Optimizing Video Selection LIMIT Queries With Commonsense Knowledge	2024	VLDB
4	5,813	Efficient Algorithms for Crowd-Aided Categorization	2020	VLDB
5	4,136	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS
6	11,790	Minimization of Classifier Construction Cost for Search Queries	2020	SIGMOD
7	3,162	Efficiently Approximating Selectivity Functions using Low Overhead Regression Models	2020	VLDB
8	11,624	Accelerating Queries over Unstructured Data with ML	2021	CIDR
9	3,907	Accelerating Approximate Aggregation Queries with Expensive Predicates	2021	VLDB
10	9,353	On Efficient Approximate Queries over Machine Learning Models	2023	VLDB