Priority sampling for estimation of arbitrary subset sums-猫眼课题宝

用于估计任意子集和的优先采样

DOI：

10.1145/1314690.1314696

发表时间：

2007

期刊：

J. ACM

影响因子：

通讯作者：

中科院分区：

文献类型：

作者：

N. Duffield;C. Lund;M. Thorup

我们希望从大量的加权项流中创建一定有限大小的通用样本，稍后可以使用该样本来估计任意子集的总权重。应用于互联网流量分析，这些项目可以是总结路由器传输的数据包流的记录。子集可以是来自蠕虫攻击的不同时间间隔的流记录，其特征稍后确定。因此，过去采集的样本使我们能够追踪攻击的历史，即使在采样时蠕虫是未知的。即使在重尾分布中，大部分权重集中在少数重项上，样本的估计也必须准确。我们希望样品对重量敏感，优先考虑重的物品。与此同时，我们希望抽样不更换，以避免多次选择沉重的项目。为了满足这些要求，我们引入了优先级采样，这是第一个权重敏感的采样方案，无需替换，适用于流媒体环境，适合于估计子集和。测试优先级抽样对互联网流量分析，我们发现它执行一个数量级优于以前的计划。优先级抽样的定义和实现都很简单：我们考虑一组i= 0，...，n-1的项目，权重为wi。对于每个项目i，我们生成一个随机数αi ∈（0，1]，并创建一个优先级qi=wi/αi。样本S由k个最高优先级的项目组成。设τ为第（k+ 1）个最高优先级。S中的每个采样项i都得到一个权重估计值i= max{wi，τ}，而非采样项得到的权重估计值i= 0。神奇的是，结果证明权重估计是无偏的，即E[i] =wi，并且通过期望的线性，我们只需将子集中的采样权重估计相加即可获得任何子集和的无偏估计。此外，我们可以估计估计值的方差，并且令人惊讶地发现，不同权重的估计值i和j 最后，我们猜想一个非常强的近似最优性，即对于任何权重序列，不存在专门的计划，抽样k个项目的无偏权重估计，得到更小的方差和比优先级抽样k+ 1个项目。Szegedy在STOC'06上解决了这个猜想。

From a high-volume stream of weighted items, we want to create a generic sample of a certain limited size that we can later use to estimate the total weight of arbitrary subsets. Applied to Internet traffic analysis, the items could be records summarizing the flows of packets streaming by a router. Subsets could be flow records from different time intervals of a worm attack whose signature is later determined. The samples taken in the past thus allow us to trace the history of the attack even though the worm was unknown at the time of sampling. Estimation from the samples must be accurate even with heavy-tailed distributions where most of the weight is concentrated on a few heavy items. We want the sample to be weight sensitive, giving priority to heavy items. At the same time, we want sampling without replacement in order to avoid selecting heavy items multiple times. To fulfill these requirements we introduce priority sampling, which is the first weight-sensitive sampling scheme without replacement that works in a streaming context and is suitable for estimating subset sums. Testing priority sampling on Internet traffic analysis, we found it to perform an order of magnitude better than previous schemes. Priority sampling is simple to define and implement: we consider a steam of items i = 0,…,n − 1 with weights wi. For each item i, we generate a random number αi ∈ (0,1] and create a priority qi = wi/αi. The sample S consists of the k highest priority items. Let τ be the (k + 1)th highest priority. Each sampled item i in S gets a weight estimate ŵi = max{wi, τ}, while nonsampled items get weight estimate ŵi = 0. Magically, it turns out that the weight estimates are unbiased, that is, E[ŵi] = wi, and by linearity of expectation, we get unbiased estimators over any subset sum simply by adding the sampled weight estimates from the subset. Also, we can estimate the variance of the estimates, and find, surprisingly, that the covariance between estimates ŵi and ŵj of different weights is zero. Finally, we conjecture an extremely strong near-optimality; namely that for any weight sequence, there exists no specialized scheme for sampling k items with unbiased weight estimators that gets smaller variance sum than priority sampling with k + 1 items. Szegedy settled this conjecture at STOC'06.

Priority sampling for estimation of arbitrary subset sums

用于估计任意子集和的优先采样

文献摘要

被引文献

相似文献