Como calcular a mediana usando MapReduce?

O cálculo da mediana usando MapReduce não é trivial, pois a mediana requer uma ordenação global dos dados. A ideia principal:

1. Map: cada mapeador lê uma parte dos dados e cria uma histograma ou distribuição de valores (por exemplo, contando o número de elementos em certos intervalos).

2. Reduce: os redutores agregam esses histogramas, obtendo uma distribuição geral em todo o conjunto de dados.

3. Determinação da mediana: usando a distribuição agregada, eles calculam a posição da mediana (metade do total de elementos) e encontram o intervalo de valores correspondente.

4. Se necessário, executam um MapReduce adicional para filtrar os dados que caem nesse intervalo e determinar mais precisamente a mediana.

Dessa forma, a mediana é calculada de forma iterativa, reduzindo o intervalo de busca usando a distribuição de dados, ao invés de ordenar todo o conjunto.

Assim funciona geralmente o algoritmo:

Map:
  para cada elemento, emite (chave_intervalo, 1)

Reduce:
  soma a quantidade por chaves

Após o Reduce:
  calcula a distribuição acumulada e encontra o intervalo com a mediana

Se o intervalo for muito grande:
  repete o MapReduce para os elementos nesse intervalo

As iterações continuam até encontrar o valor exato da mediana.