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: 12095
Venue: VLDB
Year: 2020
Pagerank: 6.9763548e-05
Overall Rank: 3,553 | 75.31%
DOI: 10.14778/3407790.3407804

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 21 of 21 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,291	Jointly Optimizing Preprocessing and Inference for DNN-based Visual Analytics	2021	VLDB	7.2607192e-05
4,492	TASTI: Semantic Indexes for Machine Learning-based Queries over Unstructured Data	2022	SIGMOD	6.1374891e-05
4,565	Optimizing Video Analytics with Declarative Model Relationships	2023	VLDB	6.0746821e-05
4,642	VIVA: An End-to-End System for Interactive Video Analytics	2022	CIDR	6.0214283e-05
4,703	Accelerating Approximate Aggregation Queries with Expensive Predicates	2021	VLDB	5.9793615e-05
5,062	Optimizing Machine Learning Inference Queries with Correlative Proxy Models	2022	VLDB	5.7172262e-05
6,306	Seiden: Revisiting Query Processing in Video Database Systems	2023	VLDB	5.1146055e-05
7,334	Aero: Adaptive Query Processing of ML Queries	2025	SIGMOD	4.7538944e-05
7,911	Accelerating Aggregation Queries on Unstructured Streams of Data	2023	VLDB	4.6143141e-05
8,464	Semantic Operators and Their Optimization: Enabling LLM-Based Data Processing with Accuracy Guarantees in LOTUS	2025	VLDB	4.5003888e-05
9,311	On Efficient Approximate Queries over Machine Learning Models	2023	VLDB	4.3535588e-05
9,767	TVM: A Tile-based Video Management Framework	2024	VLDB	4.2815042e-05
9,772	Everest: A Top-K Deep Video Analytics System	2022	SIGMOD	4.2815042e-05
9,788	Demonstration of Accelerating Machine Learning Inference Queries with Correlative Proxy Models	2022	VLDB	4.2799988e-05
9,789	RALF: Accuracy-Aware Scheduling for Feature Store Maintenance	2024	VLDB	4.2786659e-05
10,064	Cut Costs, Not Accuracy: LLM-Powered Data Processing with Guarantees	2026	SIGMOD	4.1905499e-05
10,187	On Efficient Approximate Aggregate Nearest Neighbor Queries over Learned Representations	2026	SIGMOD	4.1905499e-05
10,215	Task Cascades for Efficient Unstructured Data Processing	2026	SIGMOD	4.1905499e-05
10,394	MAST: Towards Efficient Analytical Query Processing on Point Cloud Data	2025	SIGMOD	4.1905499e-05
10,532	Scalable Complex Event Processing on Video Streams	2025	SIGMOD	4.1905499e-05
11,429	Accelerating Queries over Unstructured Data with ML	2021	CIDR	4.1905499e-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
14	Online Aggregation	1997	SIGMOD	0.0010813443
60	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00064450997
140	Predicate Migration: Optimizing Queries with Expensive Predicates	1993	SIGMOD	0.00042289025
216	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00033560137
316	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00027981848
317	NoScope: Optimizing Neural Network Queries over Video at Scale	2017	VLDB	0.0002798145
332	Accelerating Machine Learning Inference with Probabilistic Predicates	2018	SIGMOD	0.00027173479
380	Towards Estimation Error Guarantees for Distinct Values	2000	PODS	0.00024943236
398	Mergeable Summaries	2012	PODS	0.00024383201
416	Approximate Query Processing Using Wavelets	2000	VLDB	0.00023773968
694	BlazeIt: Optimizing Declarative Aggregation and Limit Queries for Neural Network-Based Video Analytics	2020	VLDB	0.00018031141
1,093	Minimal Probing: Supporting Expensive Predicates for Top-k Queries	2002	SIGMOD	0.00014123221
1,867	Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems	2014	SIGMOD	0.00010264932
2,954	Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries	2018	VLDB	7.8218804e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,062	Optimizing Machine Learning Inference Queries with Correlative Proxy Models	2022	VLDB	5.7172262e-05
8,383	Consistent and Flexible Selectivity Estimation for High-Dimensional Data	2021	SIGMOD	4.5261239e-05
8,646	Optimizing Video Selection LIMIT Queries With Commonsense Knowledge	2024	VLDB	4.4720866e-05
5,744	Efficient Algorithms for Crowd-Aided Categorization	2020	VLDB	5.343155e-05
4,439	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS	6.1806955e-05
11,599	Minimization of Classifier Construction Cost for Search Queries	2020	SIGMOD	4.1905499e-05
3,955	Efficiently Approximating Selectivity Functions using Low Overhead Regression Models	2020	VLDB	6.5895015e-05
11,429	Accelerating Queries over Unstructured Data with ML	2021	CIDR	4.1905499e-05
4,703	Accelerating Approximate Aggregation Queries with Expensive Predicates	2021	VLDB	5.9793615e-05
9,311	On Efficient Approximate Queries over Machine Learning Models	2023	VLDB	4.3535588e-05