当数据流中的点具有相关权重时，是否有一种算法可以执行水库采样？
问问题
6129 次
2 回答
22
Pavlos Efraimidis 和 Paul Spirakis 的算法正好解决了这个问题。带有完整证明的原始论文发表在 Information Processing Letters 2006 中，标题为“Weighted random sampling with a reactor”，但您可以在此处找到一个简单的摘要。
该算法的工作原理如下。首先观察另一种解决未加权水库采样的方法是为每个元素分配一个介于 0 和 1 之间的随机 id R，并逐步（例如使用堆）跟踪前 k 个 id。现在让我们看一下加权版本，假设第 i 个元素的权重为 w_i。然后，我们通过选择第 i 个元素的 id 为 R^(1/w_i) 来修改算法，其中 R 再次均匀分布在 (0,1) 中。
另一篇讨论这个算法的文章是Cloudera的这篇文章。
于 2013-08-16T21:30:22.953 回答
4
于 2013-07-18T13:09:22.543 回答