Abstract: Recently, both industrial and academic worlds suffer from the problem of incomplete data. Incomplete data（missing value） significantly reduces the value of data. Existing missing data imputation techniques with high time complexity hardly meet the requirements of real-time applications in the big data era. This paper focuses on how to efficiently evaluate aggregation queries on incomplete data. Specifically, missing data imputation techniques are integrated with the sample-based approximate query processing. Besides, a block-level sampling strategy is adoptd to speed up the query processing. All missing values are imputed in the sample and an unbiased estimator of the truth aggregate result is derived. Experiments on both real dataset and synthetic dataset show that the method can produce significant improvements in speed while providing good quality answer.

Key words: incomplete data, aggregate query, block sampling

摘要： 近年来，工业界和学术界面临着非常严重的数据缺失问题，缺失值极大降低了数据可用性。现有的缺失值填充技术需要较大的时间开销，很难满足大数据查询实时性的需求，为此，研究在有缺失值的情况下高效处理聚集查询，将基于采样的近似聚集查询处理与缺失值填充技术有效的结合，快速返回满足用户需求的聚集结果。采用基于块（block-level）的采样策略，在采集到的样本上进行缺失值填充，并根据缺失值填充的结果重构得到聚集结果的无偏估计。真实数据集和合成数据集上的实验结果表明，该文的方法比当前最好的方法在保证相同精度的前提下，大大提升了查询效率。

关键词: 缺失值填充, 聚集查询, 块采样