Stream Aggregation Through Order Sampling
Stream Aggregation Through Order Sampling
复制标题
DOI：
10.1145/3132847.3133042
复制
发表时间：
2017-03
期刊：
影响因子：
--
通讯作者：
N. Duffield;Yunhong Xu;Liangzhen Xia;Nesreen Ahmed;Minlan Yu
中科院分区：
文献类型：
--
作者：
N. Duffield;Yunhong Xu;Liangzhen Xia;Nesreen Ahmed;Minlan Yu
提出了一种新的单通道水库加权采样汇流算法--基于优先级的汇流算法(PBA)。虽然顺序抽样是从唯一关键字项流中进行加权抽样的一种强大而高效的方法，但目前还没有在非唯一关键字上的流聚集的上下文中实现顺序抽样的好处的算法。一种天真的方法是对样本进行排序，而不考虑关键字，然后聚合结果，这是效率低下得无可救药的。与之不同的是，我们提出的算法在缓存中每个密钥的生命周期内使用单个持久随机变量，并维护可以在流中的任何点查询的密钥聚合的无偏估计。基本方法可以补充一个采样和保持预采样阶段，并由PBA控制采样率自适应。与现有技术相比，该方法在调整采样和保持以操作固定高速缓存大小方面的计算复杂性有相当大的降低。关于统计性质，我们证明了PBA提供了对真实聚集体的无偏估计。我们分析了PBA及其变体的计算复杂性，并对其在合成数据和跟踪数据上的准确性进行了详细的评估。相对于自适应采样和保持，加权相对误差在5%到17%的采样率下减少了40%到65%；RANK查询也有很大的改进。
This paper introduces a new single-pass reservoir weighted-sampling stream aggregation algorithm, Priority-Based Aggregation (PBA). While order sampling is a powerful and efficient method for weighted sampling from a stream of uniquely keyed items, there is no current algorithm that realizes the benefits of order sampling in the context of stream aggregation over non-unique keys. A naive approach to order sample regardless of key then aggregate the results is hopelessly inefficient. In distinction, our proposed algorithm uses a single persistent random variable across the lifetime of each key in the cache, and maintains unbiased estimates of the key aggregates that can be queried at any point in the stream. The basic approach can be supplemented with a Sample and Hold pre-sampling stage with a sampling rate adaptation controlled by PBA. This approach represents a considerable reduction in computational complexity compared with the state of the art in adapting Sample and Hold to operate with a fixed cache size. Concerning statistical properties, we prove that PBA provides unbiased estimates of the true aggregates. We analyze the computational complexity of PBA and its variants, and provide a detailed evaluation of its accuracy on synthetic and trace data. Weighted relative error is reduced by 40% to 65% at sampling rates of 5% to 17%, relative to Adaptive Sample and Hold; there is also substantial improvement for rank queries.