Sequential reservoir sampling with a nonuniform distribution
Sequential reservoir sampling with a nonuniform distribution
复制标题
DOI：
10.1145/1141885.1141891
复制
发表时间：
2006-06
期刊：
影响因子：
--
通讯作者：
M. Kolonko;D. Wäsch
中科院分区：
文献类型：
--
作者：
M. Kolonko;D. Wäsch
我们提出了一种简单的算法，允许从数据项流中进行采样，而无需提前知道数据项的数量，也无需将所有数据项存储在主内存中。采样分布可以是一般的，即，选择数据项i的概率可以取决于单独的项。这些算法的主要优点是它们只需传递一次数据项即可产生任意大小 n 的样本。我们给出了带放回和不带放回采样的算法的不同变体，并分析了它们的复杂性。我们概括了 Knuth 早期关于具有均匀采样分布的水库采样的结果。这里考虑的一般分布允许我们以等于数据项在整个项目集中的相对权重（或适合度）的概率对项目进行采样。应用包括启发式优化程序，例如遗传算法，其中解决方案是从群体中采样的，其概率与其适应度成正比。
We present a simple algorithm that allows sampling from a stream of data items without knowing the number of items in advance and without having to store all items in main memory. The sampling distribution may be general, that is, the probability of selecting a data item i may depend on the individual item. The main advantage of the algorithms is that they have to pass through the data items only once to produce a sample of arbitrary size n.We give different variants of the algorithm for sampling with and without replacement and analyze their complexity. We generalize earlier results of Knuth on reservoir sampling with a uniform sampling distribution. The general distribution considered here allows us to sample an item with a probability equal to the relative weight (or fitness) of the data item within the whole set of items. Applications include heuristic optimization procedures such as genetic algorithms where solutions are sampled from a population with probability proportional to their fitness.