用10000台電腦找中位數

[sorryChen (陳揚和)]

其實這個Mapper/Reducer的問題
給定很多很大的檔, 每個檔各有1TB個數(memory 放不下)
如何用10000個Mapper+Reducer 找所有數的中位數呢?

我自己是想先讓每台若用selection method在Mapper 把每個檔的數分成兩堆
一堆比較大的數 一堆比較小的數, 可能分堆用pivot的個數算第三堆

但在reducer階段要怎麼靠這些訊息找中位數呢

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 207.151.93.199
推 Foremanytz:總資料量已知?未知?還在變動中?
推 Wush978:若先把資料範圍分成若干組, 各電腦統計自
→ Wush978:己的資料在各組的範圍的個數, 就可以得知
→ Wush978:中位數落在那一組, 重複做起次就可能把資
→ Wush978:料縮小到好處理的範圍了
→ yauhh:樓上這樣是否意味有個mapper是從各電腦送到
→ yauhh:要比對範圍的該電腦,套到每筆資料比對一下?
→ yauhh:可是如果各電腦沒有統計不在其他各組範圍的
→ yauhh:數字是多少個大,多少個少,要怎麼定位範圍及
→ yauhh:中位數落在哪一組?
→ sorryChen:謝謝諸位大師, 總量想成已知,固定
→ sorryChen:請問實計上要怎麼好的"分組"呢
→ sorryChen:其實我只有寫過一輪mapper/reducer
→ sorryChen:要怎麼把上個mapper/reducer的結果
→ sorryChen:送到下個mapper/reducer用呢?
→ sorryChen:output檔案嗎?
→ yauhh:不敢,你有實務經驗,你才是前輩.
→ yauhh:看手冊,只看到output有檔案方式......
→ damody:要排序後才知道吧？中位的中位不是中位
推 hilorrk:是要精準的中位數, 還是能夠容許誤差?
→ sorryChen:精準的中位應該比較難, 但selection
→ sorryChen:應該不用排完吧