Bit-Oriented Sampling for Aggregation on Big Data

摘要

The efficiency of big data analysis has become a bottleneck. Aggregation is a fundamental analytical task. It usually consumes a lot of time so that sampling based aggregation is often used to improve response time at a loss of result accuracy. In all of the related works, sampling is conducted at the granularity of data item. Considering the bits at different bit positions of each data item have different contributions to an aggregation result, the performance of sampling based aggregation has a chance of being improved if sampling is conducted at the granularity of bit. Thus, this paper studies bit-oriented sampling for aggregation. Two methods of bit-oriented uniform sampling based aggregation, i.e., DVBM and DVFM, are proposed which are based on the central limit theorem or the Chebyshev's inequality. They are much more efficient than the methods of the traditional data-oriented uniform sampling based aggregation. DVBM can guarantee a given error bound of aggregation with the assumption that sample variance equals dataset variance. By contrast, DVFM achieves the same goal without that assumption, but it could result in a larger sampling size. Extensive experiments are carried out and the results show that DVBM and DVFM are both efficient and effective.