Вычислительная медиана на карте уменьшить

Question

Может ли кто-нибудь пример вычисления медианных/квантилей на карте уменьшить?

Мое понимание медианы Datafu является то, что «п» картостроители сортировать данные и отправить данные «1» редуктор, который отвечает за сортировку все данные из п картографов и найти медиану (среднее значение) Правильно ли я понимаю ?,

если да, то подходит ли этот масштаб для массивных данных, так как я могу четко видеть один единственный редуктор изо всех сил пытается выполнить конечную задачу. Спасибо

Answer 1

Попытка найти среднее значение (среднее число) в серии потребует, чтобы 1 редуктор прошел весь диапазон чисел, чтобы определить, какое значение является «средним».

В зависимости от диапазона и уникальности значений в вашем наборе входных данных вы можете ввести объединитель для вывода частоты каждого значения - уменьшение количества выходов карты, отправленных на ваш единственный редуктор. Затем ваш редуктор может использовать пары значений/частоты для идентификации медианы.

Другой способ, которым вы могли бы масштабировать это (опять же, если вы знаете диапазон и грубое распределение значений), - это использовать пользовательский разделитель, который распределяет ключи по диапазонам (0-99 переходит к редуктору 0, 100-199 к редуктору 2 и т. Д.). Тем не менее это потребует некоторой дополнительной работы для изучения выходов редуктора и выполнения окончательного медианного расчета (зная, например, количество ключей в каждом редукторе, вы можете рассчитать, какой выход редуктора будет содержать медианный и с каким смещением)

Answer 2

O ((n log n)/p), чтобы отсортировать его, а затем O (1), чтобы получить медиану.

Да ... вы можете получить O (n/p), но вы не можете использовать функции сортировки вне коробки в Hadoop. Я бы просто сортировал и получал элемент центра, если вы не можете оправдать 2-20 часов разработки, чтобы закодировать параллельный k-й алгоритм.

Answer 3

Вам действительно нужен точный медиан и квантили?

Много времени, вам лучше всего получать приблизительные значения и работать с ними, в частности, если вы используете это для, например, разделение данных.

В самом деле, вы можете использовать приближенные квантили для ускорения нахождения точных квантилей (на самом деле в O(n/p) времени), здесь грубый набросок стратегии:

1. Есть картографа для каждого partition вычислить требуемые квантили и вывести их в новый набор данных. Этот набор данных должен быть в несколько порядков меньших величин (если вы не запрашиваете слишком много квантилей!)
2. В этом наборе данных вычислите квантили снова, похожее на «медиану медианов». Это ваши первоначальные оценки.
3. Перегруппируйте данные в соответствии с этими квантилями (или даже дополнительные разделы, полученные таким образом). Цель состоит в том, что в конечном итоге истинный квантиль гарантированно находится в одной секции, и в каждом разделе должно быть не более одного из желаемых квантилей.
4. В каждом из разделов выполните QuickSelect (в O(n)), чтобы найти истинный квантиль.

Каждый из этапов находится в линейном времени. Самым дорогостоящим шагом является часть 3, так как потребуется перераспределение всего набора данных, поэтому он генерирует сетевой трафик O(n). Возможно, вы можете оптимизировать процесс, выбрав «альтернативные» квантиля для первой итерации. Скажем, вы хотите найти глобальную медиану. Вы не можете легко найти его в линейном процессе, но вы можете, возможно, сузить его до 1/kth набора данных, когда он разбит на k разделов. Поэтому вместо того, чтобы каждый узел сообщал свою медиану, каждый узел дополнительно сообщает об объектах в (k-1)/(2k) и (k + 1)/(2k). Это должно позволить вам сузить диапазон значений, где истинный медианный должен подписать. Итак, на следующем шаге вы можете каждый узел отправлять те объекты, которые находятся в пределах требуемого диапазона, на один главный узел и выбирать медианную только в этом диапазоне.

Answer 4

Во многих реальных сценариях мощность значений в наборе данных будет относительно небольшой. В таких случаях задача может быть эффективно решена с двумя MapReduce рабочих мест:

1. Вычислить частоты значений в наборе данных (Word Count работу, в основном)
2. Идентичность картографа + редуктор, который вычисляет медиану на основе < значения - частота> пары

Работа 1. значительно сократит объем данных и может быть выполнена полностью параллельно. Редуктор задания 2. должен обрабатывать только n (n = cardinality of your value set), а не все значения, как с наивным подходом.

Ниже приведен пример редуктора задания 2. Это скрипт python, который можно использовать непосредственно в потоке Hadoop. Предполагает значения в наборе данных являются ints, но могут быть легко приняты для double s

import sys 

item_to_index_range = [] 
total_count = 0 

# Store in memory a mapping of a value to the range of indexes it has in a sorted list of all values 
for line in sys.stdin: 
    item, count = line.strip().split("\t", 1) 
    new_total_count = total_count + int(count) 
    item_to_index_range.append((item, (total_count + 1, new_total_count + 1))) 
    total_count = new_total_count 

# Calculate index(es) of middle items 
middle_items_indexes = [(total_count/2) + 1] 
if total_count % 2 == 0: 
    middle_items_indexes += [total_count/2] 

# Retrieve middle item(s) 
middle_items = [] 
for i in middle_items_indexes: 
    for item, index_range in item_to_index_range: 
     if i in range(*index_range): 
      middle_items.append(item) 
      continue 

print sum(middle_items)/float(len(middle_items)) 

Этот ответ основывается на вершине предложения первоначально поступающего из answer из Chris White. Ответ предполагает использование объединителя в качестве среднего для вычисления частот значений. Однако в MapReduce комбайнеры не гарантируются всегда. Это имеет некоторые побочные эффекты:

• редуктор должен сначала вычислить конечные цифры < пары значений, а затем вычислить медианную.
• В худшем случае, сумматоры никогда не будет выполнены, а редуктор все равно придется бороться с обработкой всех индивидуальных значений