Kā aprēķināt mediānu, izmantojot MapReduce?

MapReduce palīdzība mediānas aprēķināšanā nav vienkārša uzdevums, jo mediāna prasa globālu datu sakārtošanu. Galvenā ideja:

1. Map: katrs mapper lasa daļu no datiem un izveido histogrammu vai sadalījumu (piemēram, skaita elementu skaitu noteiktās diapazonos).

2. Reduce: reduceri apvieno šīs histogrammas, iegūstot kopējo sadalījumu visā datu kopā.

3. Mediānas noteikšana: izmantojot apkopoto sadalījumu, viņi aprēķina mediānas pozīciju (pusi no kopējā elementu skaita) un atrod atbilstošo diapazonu.

4. Ja nepieciešams, tiek veikts papildu MapReduce, lai filtrētu datus šajā diapazonā un precīzāk noteiktu mediānu.

Tādējādi mediāna tiek aprēķināta iteratīvi, sašaurinot meklēšanas diapazonu, izmantojot datu sadalījumu, nevis sakārtojot visu kopu.

Algoritms parasti darbojas šādi:

Map:
  katram elementam emit (diapazona_atslēga, 1)

Reduce:
  saskaita skaitu pēc atslēgām

Pēc Reduce:
  aprēķina kumulatīvo sadalījumu un atrod mediānas diapazonu

Ja diapazons ir pārāk liels:
  atkārto MapReduce ar elementiem šajā diapazonā

Iterācijas turpinās līdz tiek atrasta precīza mediānas vērtība.