Proof: Accelerating Approximate Aggregation Queries with Expensive Predicates
This work provides a theoretical foundation for efficient data processing in databases or analytics, though it appears incremental as it analyzes an existing method.
The paper tackles the problem of accelerating approximate aggregation queries with expensive predicates by theoretically analyzing the ABae method, showing that its mean squared error decays at a rate of O(N^{-1}) when budget is allocated properly, matching the optimal stratified sampling algorithm.
Given a dataset $\mathcal{D}$, we are interested in computing the mean of a subset of $\mathcal{D}$ which matches a predicate. ABae leverages stratified sampling and proxy models to efficiently compute this statistic given a sampling budget $N$. In this document, we theoretically analyze ABae and show that the MSE of the estimate decays at rate $O(N_1^{-1} + N_2^{-1} + N_1^{1/2}N_2^{-3/2})$, where $N=K \cdot N_1+N_2$ for some integer constant $K$ and $K \cdot N_1$ and $N_2$ represent the number of samples used in Stage 1 and Stage 2 of ABae respectively. Hence, if a constant fraction of the total sample budget $N$ is allocated to each stage, we will achieve a mean squared error of $O(N^{-1})$ which matches the rate of mean squared error of the optimal stratified sampling algorithm given a priori knowledge of the predicate positive rate and standard deviation per stratum.