A sample-and-clean framework for fast and accurate query processing on dirty data

Aggregate query processing over very large datasets can be slow and prone to error due to dirty (missing, erroneous, du-plicated, or corrupted) values. To address the speed issue, there has lately been a resurgence of interest in sampling-based approximate query processing, but this approach fur-ther reduces answer quality by introducing sampling error. In this paper, we explore an intriguing opportunity that sampling presents, namely, that when integrated with data cleaning, sampling actually improves answer quality. Data cleaning requires either domain-specific software (which can be costly and time-consuming to develop) or human inspec-tion. The latter is increasingly feasible with crowdsourcing but can be highly inefficient for large datasets. Our ap-proach requires cleaning only samples from the dataset to process aggregate numerical queries such as average, sum, count, variance, geometric mean, and product. We derive confidence intervals as a function of sample size and show how our approach reduces error bias. We provide a detailed evaluation of our approach using datasets and workloads from the TPC-H benchmark, an on-line citation index and a database of indoor sensor network values. Our results sug-gest that estimated values can rapidly converge toward the true values with surprisingly few cleaned samples, offering significant improvement in cost over cleaning all of the data and significant improvement in accuracy over cleaning none of the data. 1