Rapid Approximate Aggregation with Distribution-Sensitive Interval Guarantees
Rapid Approximate Aggregation with Distribution-Sensitive Interval Guarantees
复制标题
DOI：
10.1109/icde51399.2021.00150
复制
发表时间：
2020-08
期刊：
影响因子：
--
通讯作者：
Stephen Macke;M. Aliakbarpour;Ilias Diakonikolas;Aditya G. Parameswaran;R. Rubinfeld
中科院分区：
文献类型：
--
作者：
Stephen Macke;M. Aliakbarpour;Ilias Diakonikolas;Aditya G. Parameswaran;R. Rubinfeld
聚合数据是数据分析、数据探索和OLAP的基础。近似查询处理（AQP）技术通常用于加速使用样本的聚集计算，其中置信区间（CI）被广泛用于量化相关误差。实践中使用的CI分为两类：严格但不正确的技术，即，它们产生紧密的间隔，但仅提供渐近保证，使得它们不可靠，或者是正确但不紧密的技术，即，它们提供了严格的保证，但过于保守，导致置信区间过于宽松而无法使用。在本文中，我们开发了一种CI技术，这是正确的和更严格的比传统的方法。从保守的CI开始，我们确定了他们经常面临的两个问题：悲观质量分配（PMA）和幻影离群值敏感性（PHOS）。通过开发一种新的范围修剪技术，消除PHOS和配对它与已知的CI技术没有PMA，我们开发了一种技术，用于计算CI具有较强的保证，需要较少的样本相同的宽度。我们在一个采样优化的内存列存储下实现了我们的技术，并展示了它们如何加速涉及真实的数据集上的聚合的查询，与传统的AQP保证和精确方法相比，典型的加速比为10倍，同时遵守精度约束。
Aggregating data is fundamental to data analytics, data exploration, and OLAP. Approximate query processing (AQP) techniques are often used to accelerate computation of aggregates using samples, for which confidence intervals (CIs) are widely used to quantify the associated error. CIs used in practice fall into two categories: techniques that are tight but not correct, i.e., they yield tight intervals but only offer asymptoticguarantees,makingthem unreliable, or techniques that are correct but not tight, i.e., they offer rigorous guarantees, but are overly conservative, leading to confidence intervals that are too loose to be useful. In this paper, we develop a CI technique that is both correct and tighter than traditional approaches. Starting from conservative CIs, we identify two issues they often face: pessimistic mass allocation (PMA) and phantom outlier sensitivity (PHOS). By developing a novel range-trimming technique for eliminating PHOS and pairing it with known CI techniques without PMA, we develop a technique for computing CIs with strong guarantees that requires fewer samples for the same width. We implement our techniques underneath a sampling-optimized in-memory column store and show how they accelerate queries involving aggregates on real datasets with typical speedups on the order of 10× over both traditional AQP-with-guarantees and exact methods, all while obeying accuracy constraints.