使用MapReduce在MongoDB中的累积分布

Question

>我在mongodb中有一个文档集合，我想计算某些属性的CDF并将其返回或存储在数据库中。显然，为每个文档添加新属性不是一个好方法，我可以使用以后可以使用的近似值。这更像是一个理论问题。

因此，我使用mapreduce作业在离散间隔上计算CDF的采样，如下所示（只是算法）：

1. 获取属性someAttr的count、min和max
2. 假设min = 5、max=70、count = 200。
3. 在map() ： for (i=this.someAttr; i < max+1; i++) { emit(i, 1) }
4. 在reduce()中，只需返回每个键的总和。
5. 在 finalize() 中，将减少的输出除以记录计数：return val / count 。

但是，这确实会输出包含来自 CDF 的示例的集合。

如您所见，这里的间隔步骤是1，但是这种方法的巨大低效率在于，即使只有少数文档在集合中，即使只有少数文档，也可能有大量的发射，因此这显然是不可扩展的，并且不起作用。

输出如下所示：

{ _id: 5, val: 0}
{ _id: 6, val: 0.04}
{ _id: 7, val: 0.04}
...
{ _id: 71, val: 1.0}

从这里，我可以轻松地获得任何值的 CDF 的近似值，或者如果合理的话，甚至可以在它们之间进行插值。

有人可以告诉我如何使用MapReduce（或者可能没有MapReduce）计算CDF的（样本）吗？

Answer 1

根据定义，属性a的累积分布函数F_a由下式定义

F_a(x) = # documents with attribute value <= x / # of documents

因此，您可以使用

F_a(x) = db.collection.count({ "a" : { "lte" : x }) / db.collection.count({ "a" : { "$exists" : true } })

分母中的计数假定您不想计算缺少a字段的文档。a指数将使这一速度变得很快。

您可以使用它来计算 cdf 的样本，或者只是按需计算 cdf。无需地图缩减。