Fast Approximate Aggregation with Error Guarantee Using Encoded Bit-Slice Indexing
摘要
We propose error-range-guarantee approximate-aggregation methods called patch based encoding plus deterministic approximate querying (PBE+DAQ) and its extension, PBE+DAQ/WN (Wide-Narrow), which perform better than conventional DAQ by reducing the amount of data to be computed. With the increase in data volume, fast data analysis is required, and aggregation operations play an important role in data analysis. However, the larger the data volume, the longer time is required for aggregation operations. In many cases, while fast approximate-aggregation operations are required rather than accurate operations, the approximation error must be guaranteed. We use PBE for compressing the majority of data for faster aggregation operations and DAQ for error-guarantee approximation. We also developed cost models for the two methods as well as for conventional DAQ. We implemented the proposed methods and conducted experiments using real-world datasets. The experimental results indicate that the execution times of PBE+DAQ and PBE+DAQ/WN are 1.1x to 1.2x faster than that of DAQ while guaranteeing the error range of the aggregation results.