On the Variance of Subset Sum Estimation
On the Variance of Subset Sum Estimation
复制标题
关于子集和估计的方差
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
M. Thorup
中科院分区：
文献类型：
--
作者：
M. Szegedy;M. Thorup
对于大容量数据流和大型数据仓库，采样被用来获得高效的近似答案，以聚合选定子集上的查询。我们正在处理的可能是一组重尾的权重项。我们要解决的问题是：
我们应该使用哪种抽样方案来获得最准确的子集和估计？
我们给出了一个关于子集和估计的方差的简单定理，并用它证明了不同已知抽样方案的最优性和近最优性。本文建议的性能度量是任意给定大小的所有子集的平均方差。所谓最优，我们的意思是不存在任何一组输入权重，任何采样方案都可以具有更好的平均方差。例如，我们证明了适当加权的系统抽样对于所有子集大小都是同时最优的。更标准的方案，如均匀抽样和带替换的概率与大小成比例抽样，可能是任意糟糕的。
了解不同抽样方案的方差最优性有助于决定在给定的上下文中应用哪种抽样方案。
For high volume data streams and large data warehouses, sampling is used for efficient approximate answers to aggregate queries over selected subsets. We are dealing with a possibly heavy-tailed set of weighted items. We address the question:
Which sampling scheme should we use to get the most accurate subset sum estimates?
We present a simple theorem on the variance of subset sum estimation and use it to prove optimality and near-optimality of different known sampling schemes. The performance measure suggested in this paper is the average variance over all subsets of any given size. By optimal we mean there is no set of input weights for which any sampling scheme can have a better average variance. For example, we show that appropriately weighted systematic sampling is simultaneously optimal for all subset sizes. More standard schemes such as uniform sampling and probability-proportional-to-size sampling with replacement can be arbitrarily bad.
Knowing the variance optimality of different sampling schemes can help deciding which sampling scheme to apply in a given context.