Kuidas arvutada mediaan MapReduce abil?

MapReduce abil mediana arvutamine ei ole triviaalne ülesanne, kuna mediaan nõuab andmete globaalse järjestamise. Põhiteooria:

1. Map: iga mapper loeb osa andmetest ja loob histogrammi või jaotuse (näiteks loendades elementide arvu teatud vahemikes).

2. Reduce: reducerid ühendavad need histogrammid, saades kogu andmekogumi üldjaotuse.

3. Mediaani määramine: kasutades kogutud jaotust, arvutavad nad mediaani positsiooni (kogu elementide arv pool) ja leiavad vastava vahemiku.

4. Vajadusel käivitavad nad täiendava MapReduce, et filtreerida andmeid selles vahemikus ja määrata mediaan täpsemalt.

Nii arvutatakse mediaan iteratiivselt, kitsendades otsinguvahemikku andmete jaotuse abil, mitte kogu kogumi sorteerimise teel.

Algoritm töötab tavaliselt järgmiselt:

Map:
  iga elemendi puhul emit (vahemiku_võti, 1)

Reduce:
  summeerib arvud võtmepõhiselt

Reduce järel:
  arvutab kumulatiivse jaotuse ja leiab mediaani vahemiku

Kui vahemik on liiga suur:
  korrake MapReduce selle vahemiku elementidega

Iteratsioonid jätkuvad, kuni leitakse täpne mediaani väärtus.