Накопительное распределение в MongoDB с использованием MapReduce

Question

У меня есть коллекция документов в mongodb, и я хочу вычислить CDF для некоторых атрибутов и вернуть или сохранить их в db. Очевидно, что добавление нового атрибута в каждый документ не является хорошим подходом, и я в порядке с приближением, которое я могу использовать позже. Это скорее теоретический вопрос.

Так что я пошел с вычислением выборки ВПР на дискретные интервалы с заданием MapReduce, как это (только алгоритм):

1. Получить count, min и max атрибута someAttr
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, но огромная неэффективность такого подхода является то, что может быть чудовищным количеством излучая даже из одного документа, даже с небольшим количеством документов в colletion, следовательно, это, очевидно, не является масштабируемым и не будет работать.

Результат выглядит следующим образом:

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

Отсюда можно легко получить приближенное значение КОР для любого из значений или даже интерполировать между ними, если это разумно.

Может ли кто-нибудь дать мне представление о том, как вы могли бы вычислить (образец) CDF с помощью MapReduce (или, возможно, без MapReduce)?

Answer 1

По определению, кумулятивная функция распределения F_a для атрибута a определяется

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

Таким образом, вы можете вычислить CDF с

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

Граф в знаменатель предполагает, что вы не хотите подсчитать документы, отсутствующие в поле a. Индекс на a сделает это быстро.

Вы можете использовать это, чтобы вычислить образцы cdf или просто вычислить cdf по запросу. Нет необходимости в сокращении карты.