计算中位数减少

Question

有人可以举例说明地图中的中位数/分位数的计算吗？

我对Datafu中位数的理解是'n'映射器对数据进行排序并将数据发送到"1"reducer,它负责对n个映射器中的所有数据进行排序并找到中位数(中间值)我的理解是否正确？

如果是这样,这种方法是否适用于大量数据,因为我可以清楚地看到单个减速器正在努力完成最终任务.谢谢

Answer 1

试图找到一个系列中的中位数(中间数)将要求1个减速器传递整个数字范围以确定哪个是"中间"值.

根据输入集中值的范围和唯一性,您可以引入组合器来输出每个值的频率 - 减少发送到单个reducer的地图输出的数量.然后,您的减速器可以使用排序值/频率对来识别中位数.

另一种可以扩展它的方法(再次,如果您知道值的范围和粗略分布)是使用自定义分区器,按范围桶分配键(0-99转到减速器0,100-199到减速器2,等等上).然而,这将需要一些辅助工作来检查减速器输出并执行最终中位数计算(例如,知道每个减速器中的键数,您可以计算哪个减速器输出将包含中位数,以及在哪个偏移处)

Answer 2

你真的需要精确的中位数和分位数吗？

很多时候,你最好只获得近似值,并使用它们,特别是如果你用它来进行数据分区.

实际上,您可以使用近似分位数来加速查找精确的分位数(实际上是O(n/p)及时),这里是策略的大致轮廓:

1. 让每个分区的映射器计算所需的分位数,并将它们输出到新的数据集.这个数据集应该是几个小的放大倍数(除非你要求太多的分位数!)
2. 在此数据集中,再次计算分位数,类似于"中位数的中位数".这些是您的初步估计.
3. 根据这些分位数(或甚至以这种方式获得的其他分区)重新分配数据.目标是最终,真正的分位数保证在一个分区中,并且每个分区中最多应该有一个所需的分位数
4. 在每个分区内,执行QuickSelect(in O(n))以查找真正的分位数.

每个步骤都是线性时间.最昂贵的步骤是第3部分,因为它需要重新分配整个数据集,因此它会生成O(n)网络流量.您可以通过为第一次迭代选择"备用"分位数来优化过程.说,你想找到全球中位数.您无法轻松地在线性过程中找到它,但是当它被分成k个分区时,您可以将其缩小到数据集的1/kth.因此,不是让每个节点报告其中值,而是让每个节点另外报告(k-1)/(2k)和(k + 1)/(2k)处的对象.这应该允许您缩小真正中位数必须显着位置的值的范围.因此,在下一步中,您可以将每个节点将所需范围内的对象发送到单个主节点,并仅选择此范围内的中位数.