使用MapReduce查找大整数集的中位数

Question

有没有一种快速算法能在MapReduce框架上运行，从一个巨大的整数集合中找到中位数？

- user882107

---

可能是在MapReduce中计算中位数的重复问题。 - Jakub Kukul

Answer 1

这是我的方法。这是顺序快速选择的一种并行版本。(有些映射/减少工具可能不允许您轻松地执行此操作...)

选择一个小而任意的输入集块。按顺序对其进行排序。我们将以并行方式使用这些作为整体的枢轴。将其称为数组"pivots"，其大小为"k"。

执行如下映射/减少：对于输入集中的每个值"x"，二进制搜索以查找"x"相对于"pivots"的位置；将此位置称为"bucket(x)"。这是介于0和k之间的整数。缩小步骤是计算每个桶中的元素数量；将"bucket[b]"定义为"bucket(x)=b"的x的数量。

中位数必须在"median bucket"中。挑选出该中位数桶中的所有值，并使用传统的顺序选择算法找到具有正确索引的元素。

- Louis Wasserman

---

假设我正确理解了这个算法，它存在几个问题。首先，您应该选择具有统计学意义的枢轴数量。其次，不能保证中位数将在“中位数桶”中。例如，如果您有3个reducer，并且在排序后选择第一个和第二个数字作为枢轴，那么所有数字都将最终进入第三个reducer，而不是中位数reducer，其中什么也没有。第三，如果您将桶i中的所有内容发送到reducer i，则不能保证它将适合内存。 - delmet

“你应该选择具有统计学意义的支点数”，我指的是即使您决定只使用少量支点，也应该从比减速器数量大得多的样本中选择支点。您的算法可能已经隐含了这一点。但是，支点的数量不应该是减速器数量的函数，而应该是内存和输入大小的函数。我想你说的“中值桶”可能指的是包含中位数的存储桶，可以通过桶计数来确定。即使如此，第三个反对意见仍然存在。 - delmet

我想你所说的“中位数桶”可能指的是包含中位数的桶，你可以从桶计数中找出它。显然，这是正确的；否则我们为什么需要计数步骤呢？但是枢轴数目不应该是 reducer 数目的函数，而应该是内存和输入大小的函数。枢轴数量在这里是非常灵活的；我并没有意味着其他的意思。 - Louis Wasserman

选择一个小的、任意的输入集合块，大小大约与可用机器数量相同...我们将把它们作为一堆枢轴使用。这直接说明了另外一种方法。无论如何，你的“中位数桶”怎么知道它是中位数桶呢？ - delmet

得到桶的计数后，我们就可以弄清楚了，不是吗？ - Louis Wasserman

实际上，这是该算法的主要复杂性。最简单的方法是将桶从1到k进行标记，每个桶打印其标签、计数和值。然后简单地步骤来确定计数和相关的桶。之后，您可以过滤掉除中位数桶以外的所有内容，并找到中位数。问题在于，在MR中排序很容易，但标记很难（或不那么容易）。无论如何，所有这些讨论都为答案增加了价值。 - delmet