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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Fast Approximate Aggregation with Error Guarantee Using Encoded Bit-Slice Indexing

  • Kakeru Ito,
  • Ryogo Maeda,
  • Qiong Chang,
  • Jun Miyazaki

摘要

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.