1. Abstract
- processors快速構(gòu)建histogram假褪，把數(shù)據(jù)壓縮到固定的大小
- master processor找到近似最優(yōu)的split點(diǎn)
- 分析了算法的準(zhǔn)確性
2. Intro
- 決策樹的一大優(yōu)點(diǎn)是提供了human-readable的分類rules
- 缺點(diǎn)是需要對(duì)屬性排序以確定如何split節(jié)點(diǎn)
- 排序過(guò)于耗時(shí)的兩種解決辦法：對(duì)數(shù)據(jù)進(jìn)行預(yù)排序；用sampling或者直方圖來(lái)代替排序
- Horizontal parallelism: 切分?jǐn)?shù)據(jù)到processors
- Vertical parallelism: 切分屬性到processors
- focus on 近似算法
- 每個(gè)processor將自己數(shù)據(jù)的近似描述發(fā)送給master processor抓艳，master匯總信息，決定如何split
3. Algorithm description
- 數(shù)據(jù)切分的必要性：?jiǎn)螜C(jī)無(wú)法存儲(chǔ)应闯；無(wú)法到達(dá)單機(jī)砸喻；無(wú)法在一定時(shí)間內(nèi)處理所有數(shù)據(jù)
3.1. Histogram building
- 四個(gè)procedures：update、merge犯犁、sum、uniform
- merge：第一步女器，兩個(gè)histogram合并為一個(gè)histogram酸役；第二步，合并最近的兩個(gè)bins驾胆，保證最多只有B個(gè)bins
- uniform：將直方圖均一化涣澡，也就是每個(gè)bin里的數(shù)據(jù)數(shù)量是一樣的
3.2. Tree growing
- 停止條件：node上sample的數(shù)量；node的impurity
- 最常見的impurity函數(shù)：Gini criterion和entropy function
- 每個(gè)processor處理他們能看到的數(shù)據(jù)丧诺，建立直方圖入桂，然后發(fā)送給master processor
- 決策樹在訓(xùn)練中或者訓(xùn)練后被剪枝，為了減小樹的大小锅必，為了增強(qiáng)模型的泛化性事格；對(duì)完整的樹叢bottom到up檢測(cè)，一些子樹被剪枝搞隐，根據(jù)剪枝前后誤差的變化
3.3. 復(fù)雜度分析
- 直方圖bin的數(shù)量是固定的驹愚，直方圖的操作的時(shí)間是固定的
- 一輪迭代需要：At most N/W operations by each processor in the updating phase（N是數(shù)據(jù)大小，W是processors數(shù)量）劣纲；固定的space和communication復(fù)雜度逢捺；merge phase需要固定的時(shí)間
4. Related work
- 第一類算法有被證明的近似保證，但是需要很大的內(nèi)存癞季，需要的空間與數(shù)據(jù)大小成正比
- 第二類是啟發(fā)式的方法劫瞳，在實(shí)際中很有用，需要較少的空間開銷绷柒，但是缺少嚴(yán)格的準(zhǔn)確性分析
- 固定內(nèi)存算法會(huì)帶來(lái)準(zhǔn)確率的代價(jià)志于。當(dāng)數(shù)據(jù)分布是傾斜的，在線直方圖的準(zhǔn)確率會(huì)下降
- SPDT與SPIES和pCLOUDS的區(qū)別：第一個(gè)不同是废睦，SPIES和pClOUDS采樣數(shù)據(jù)伺绽，SPDT不采樣；第二個(gè)不同是需不需要對(duì)數(shù)據(jù)的第二輪掃描嗜湃；第三個(gè)不同是奈应，本文分析了并行樹與順序樹的error
