# Accelerating Approximate Aggregation Queries with Expensive Predicates

arXiv: https://arxiv.org/abs/2108.06313 · HTML: https://mlsanity.com/paper/2108.06313/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Aug 2021.

## Built on by (most cited first, 10 of 10)

- [Semantic Operators: A Declarative Model for Rich, AI-based Data Processing](https://mlsanity.com/paper/2407.11418/) (2024)
- [Abacus: A Cost-Based Optimizer for Semantic Operator Systems](https://mlsanity.com/paper/2505.14661/) (2025)
- [Cut Costs, Not Accuracy: LLM-Powered Data Processing with Guarantees](https://mlsanity.com/paper/2509.02896/) (2025)
- [Extract-Transform-Load for Video Streams](https://mlsanity.com/paper/2310.04830/) (2023)
- [Deep Research is the New Analytics System: Towards Building the Runtime for AI-Driven Analytics](https://mlsanity.com/paper/2509.02751/) (2025)
- [VQPy: An Object-Oriented Approach to Modern Video Analytics](https://mlsanity.com/paper/2311.01623/) (2023)
- [Beyond Linear LLM Invocation: An Efficient and Effective Semantic Filter Paradigm](https://mlsanity.com/paper/2603.04799/) (2026)
- [Hydro: Adaptive Query Processing of ML Queries](https://mlsanity.com/paper/2403.14902/) (2024)
- [Evergreen: Efficient Claim Verification for Semantic Aggregates](https://mlsanity.com/paper/2604.26180/) (2026)
- [Semantic Views: Certified Reuse of LLM Labels Across Semantic Queries](https://mlsanity.com/paper/2610.12768/) (2026)

## Abstract (arXiv)

Researchers and industry analysts are increasingly interested in computing aggregation queries over large, unstructured datasets with selective predicates that are computed using expensive deep neural networks (DNNs). As these DNNs are expensive and because many applications can tolerate approximate answers, analysts are interested in accelerating these queries via approximations. Unfortunately, standard approximate query processing techniques to accelerate such queries are not applicable because they assume the result of the predicates are available ahead of time. Furthermore, recent work using cheap approximations (i.e., proxies) do not support aggregation queries with predicates. To accelerate aggregation queries with expensive predicates, we develop and analyze a query processing algorithm that leverages proxies (ABae). ABae must account for the key challenge that it may sample records that do not satisfy the predicate. To address this challenge, we first use the proxy to group records into strata so that records satisfying the predicate are ideally grouped into few strata. Given these strata, ABae uses pilot sampling and plugin estimates to sample according to the optimal allocation. We show that ABae converges at an optimal rate in a novel analysis of stratified sampling with draws that may not satisfy the predicate. We further show that ABae outperforms on baselines on six real-world datasets, reducing labeling costs by up to 2.3x.