当数据流中的点具有关联权重时，是否存在如何执行储层采样的算法?
Pavlos Efraimidis和Paul Spirakis的算法正好解决了这个问题。完整证明的原始论文发表在《Information Processing Letters 2006》上，题目是《带水库的加权随机抽样》，但你可以在这里找到一个简单的总结。
算法的工作原理如下:首先观察到，解决未加权储存库抽样的另一种方法是为每个元素分配一个介于0到1之间的随机id R，并逐渐(例如使用堆)跟踪最前面的k个id。现在我们来看看加权版本，假设第i个元素的权重是w_i。然后，我们修改算法，选择第i个元素的id为R^(1/w_i)，其中R再次均匀分布在(0,1)中。
另一篇关于这个算法的文章是Cloudera的人写的
可以尝试S. Efraimidis这篇论文中的A-ES算法。这是相当简单的代码和非常有效的。
希望有帮助，
Benoit