小智 17
Pavlos Efraimidis和Paul Spirakis的算法正好解决了这个问题.带有完整样张的原始论文在2006年信息处理快报中以"带有水库的加权随机抽样"的标题发表,但您可以在这里找到一个简单的摘要.
该算法的工作原理如下.首先观察解决未加权油藏采样的另一种方法是为每个元素分配0和1之间的随机ID R,并逐步(比如用堆)跟踪顶部k id.现在让我们看看加权版本,让我们说第i个元素有权重w_i.然后,我们通过选择第i个元素的id为R ^(1/w_i)来修改算法,其中R再次均匀地分布在(0,1)中.
另一篇文章谈到这个算法是这样一个由Cloudera的乡亲.