mapreduce - 使用 Map Reduce 实现水库采样

Question

这个链接“ http://had00b.blogspot.com/2013/07/random-subset-in-mapreduce.html ”讨论了如何使用map reduce框架实现水库采样。我觉得他们的解决方案很复杂，以下更简单的方法会起作用。

问题： 给定大量样本，生成一个大小为 k 的集合，使得每个样本在集合中出现的概率相等。

建议的解决方案：

1. 映射操作：对于每个输入数 n，输出 (i, n)，其中 i 在 0 到 k-1 范围内随机选择。
2. 减少操作：在所有具有相同键的数字中，随机选择一个。

声明： 任何数字在 k 大小的集合中的概率是 k/n（其中 n 是样本总数）

证明直觉：

由于映射操作将每个输入样本随机分配给编号 i (0 <= i <= k-1) 的桶，因此每个桶的大小将为 n/k。现在每个数字只出现在一个桶中，假设桶 i。它在桶 i 的 reduce 操作中被选中的概率是 1/(n/k) = k/n

我将不胜感激对我的解决方案的任何第二个想法，无论它看起来是否正确。

Answer 1

你的论点有一个小缺陷。您的算法可能不会返回大小为 k 的样本，因为可能没有任何元素映射到特定键。在极端情况下（即使机会很小），所有输入元素都可能只映射到一个键，在这种情况下，您的算法只返回一个元素。

“丢失”特定密钥的事件具有概率 ((k-1)/k)^n = (1-1/k)^n，其近似为（使用泰勒近似）e^{-n/k}。如果 k 远小于 n，这可以忽略不计，但如果 k 与 n 成比例，比如 k=n/2，那么这个坏事件实际上以恒定概率发生。