论文#7 | Storyboard - Optimizing Precomputed Summaries for Aggregation

AggPre将数据进行分区, 并为每个数据段预先计算近似摘要, 从而可以在不扫描原始数据的情况下聚合和组合段摘要以估计结果——由于存储空间有限, 每个摘要都会引入影响查询精度的近似错误
Storyboard: 通过优化项目频率(item frequency)和分位数摘要(quantile summaries), 利用可用于摘要构建和聚合的额外内存来获得更精确的合并结果
第99百分位延迟查询? query for the 99th percentile latency

现实应用: 超过一半的查询跨越超过100个5分钟的片段(摘要), 由于系统以5分钟的粒度存储摘要, 这意味着要合并数百个摘要的结果, 或者恢复到不太准确、更粗粒度的汇总:

Storyboard在构建和查询时都利用了额外的内存, 以获得更高的查询精度
在接收时: 预计算摘要优化以最小化聚合下的错误
在查询时: 使用精确累加器将来自多个摘要的结果组合起来, 以提供精确的结果

查询方法g:

• 项目频率f(x): 值为x的记录总个数
• 排名r(x):值小于等于x的记录总个数

对于单个rank或frequency估计，查询处理器可以精确地相加标量:

累加器A有自己的附加误差, 在估计摘要的代理值时引入
A可以用于top-k / heavy hitter查询, 追踪摘要S1…Sk的值和个数, 然后排序A中的项目: 按值排序可以用于估计分位数quantile, 按个数排序可以用于估计heavy hitter
当内存受到限制时, 让A成为代理值(proxy values)和摘要中存储的计数(counts)的标准但非常大的流摘要

间隔查询和协作摘要

间隔查询(interval): 一维连续范围——Storyboard使用协作摘要(cooperative summaries), 针对连续摘要序列中的累积错误, 调整新摘要中的错误以进行补偿
假设对数据段D限定摘要空间s
可以选择xi, γi来最小化聚合多个摘要的查询的总错误, Storyboard显式地最小化了一组查询的错误, 每个KT段有一个固定的起点。这些聚合间隔为“prefix”间隔Pret, 是对标准前缀和范围的修改
任何相邻间隔都可以表示为对齐间隔Pret的线性组合, 如Q = A + B - C:

存储Dt中heavy hitter大于|Dt|/s的真实计数, 以及迄今为止最大的累积欠计数(highest cumulative undercount——εPret(x)), 以便St中的过大的x将根据下一个摘要中的欠计数进行调整
存储εPret(x)和r|D|/s中较小值
r越大，算法就可以在较高的局部误差和较小的汇总误差之间进行权衡

对D中的值进行排序, 并将排序后的值划分为s个大小相等的块。然后在每个块中选择一个值作为代理计数为|D|/s的代表包含在St中, 确保使用St估计任何rank误差最大为|D|/s

数据立方体

与样本大小成比例的加权概率(PPS)——PPS摘要是一个加权随机样本，它包括数据段D中与其大小或总数成比例的概率项
数据立方体 / 多维(data cube): 查询与特定维度值匹配的数据聚合, 例如loc=USA和type=TCP —— 沿单个维度显式地补偿错误不够。立方体通常有具有有偏分布的维度(dimensions with skewed value distributions): 某些值或值的组合出现的频率远远高于其他值, Storyboard可以优化存储空间的分配, 引入有针对性的偏见(targeted biases), 最小化平均查询错误