如何使用Map/Reduce选择随机(小)数据样本？

Question

我想编写一个map/reduce作业,根据行级条件从大型数据集中选择一些随机样本.我想最小化中间键的数量.

伪代码:

for each row 
  if row matches condition
    put the row.id in the bucket if the bucket is not already large enough

你做过这样的事吗？有没有众所周知的算法？

包含连续行的样本也足够好.

谢谢.

Answer 1

映射器:输出所有符合条件的值,每个值都带有一个随机整数键.

单个减速器:输出前N个值,丢弃键.

分拣机将为您随机化映射器输出顺序.您不知道映射器将找到多少个限定值,因此每个映射器必须从其分区输出所有合格值.

总的来说,我喜欢建立这样简单的映射器/缩减器工具,尽可能多地使用Hadoop机器; 我最终在不同的任务中重复使用它们.

Answer 2

Karl的方法运行得很好,但我们可以大大减少映射器生成的数据量.

设K为您想要的样本数.我们假设它足够小,可以保存在你的一个节点上.我们将为每个匹配的行分配一个随机值,然后使用选择算法的修改来查找K个最小值.

在每个映射器的设置部分,创建一个优先级队列 ; 一个Fibonnacci堆是一个很好的选择.我们将使用花车作为优先事项; 如果你有大量的数据,双打可能更适合避免存在关系.对于符合条件的每一行,将该行插入优先级队列,并将随机选择的0到1之间的浮点作为优先级.如果队列中有多个K项,请删除最高值的项(这与标准Fibonnacci堆的术语相反).

最后,在映射器的末尾,发出队列中的所有内容.对于您发出的每个项目,使用优先级作为键FloatWritable,并将相应行的某些表示用作值(行ID,或者可能是整行内容).您将仅为每个映射器发射K值(如果该映射器中的匹配行少于K个,则为更少).

在您的单个减速器中,Hadoop将按照从最低到最高的顺序自动扫描键.发出与您看到的第一个K键对应的行(K最低),然后退出.

这是有效的,因为每个匹配行具有K个最小浮点值之一的相同概率.我们跟踪每个映射器的K个最小浮点数,以确保我们不会错过任何映射器,然后将它们发送到reducer以找到整体最小的K.