Title: An Iterative Scheme for Leverage-based Approximate Aggregation,
Abstract: The current data explosion poses great challenges to the approximate
aggregation with an efficiency and accuracy. To address this problem, we
propose a novel approach to calculate the aggregation answers with a high
accuracy using only a small portion of the data. We introduce leverages to
reflect individual differences in the samples from a statistical perspective.
Two kinds of estimators, the leverage-based estimator, and the sketch estimator
(a "rough picture" of the aggregation answer), are in constraint relations and
iteratively improved according to the actual conditions until their difference
is below a threshold. Due to the iteration mechanism and the leverages, our
approach achieves a high accuracy. Moreover, some features, such as not
requiring recording the sampled data and easy to extend to various execution
modes (e.g., the online mode), make our approach well suited to deal with big
data. Experiments show that our approach has an extraordinary performance, and
when compared with the uniform sampling, our approach can achieve high-quality
answers with only 1/3 of the same sample size.