1. Abstract
- processors快速构建histogram，把数据压缩到固定的大小
- master processor找到近似最优的split点
- 分析了算法的准确性
2. Intro
- 决策树的一大优点是提供了human-readable的分类rules
- 缺点是需要对属性排序以确定如何split节点
- 排序过于耗时的两种解决办法：对数据进行预排序；用sampling或者直方图来代替排序
- Horizontal parallelism: 切分数据到processors
- Vertical parallelism: 切分属性到processors
- focus on 近似算法
- 每个processor将自己数据的近似描述发送给master processor，master汇总信息，决定如何split
3. Algorithm description
- 数据切分的必要性：单机无法存储；无法到达单机；无法在一定时间内处理所有数据
3.1. Histogram building
- 四个procedures：update、merge、sum、uniform
- merge：第一步，两个histogram合并为一个histogram；第二步，合并最近的两个bins，保证最多只有B个bins
- uniform：将直方图均一化，也就是每个bin里的数据数量是一样的
3.2. Tree growing
- 停止条件：node上sample的数量；node的impurity
- 最常见的impurity函数：Gini criterion和entropy function
- 每个processor处理他们能看到的数据，建立直方图，然后发送给master processor
- 决策树在训练中或者训练后被剪枝，为了减小树的大小，为了增强模型的泛化性；对完整的树丛bottom到up检测，一些子树被剪枝，根据剪枝前后误差的变化
3.3. 复杂度分析
- 直方图bin的数量是固定的，直方图的操作的时间是固定的
- 一轮迭代需要：At most N/W operations by each processor in the updating phase（N是数据大小，W是processors数量）；固定的space和communication复杂度；merge phase需要固定的时间
4. Related work
- 第一类算法有被证明的近似保证，但是需要很大的内存，需要的空间与数据大小成正比
- 第二类是启发式的方法，在实际中很有用，需要较少的空间开销，但是缺少严格的准确性分析
- 固定内存算法会带来准确率的代价。当数据分布是倾斜的，在线直方图的准确率会下降
- SPDT与SPIES和pCLOUDS的区别：第一个不同是，SPIES和pClOUDS采样数据，SPDT不采样；第二个不同是需不需要对数据的第二轮扫描；第三个不同是，本文分析了并行树与顺序树的error
