1. Intro
- 和其他分类方法相比，建立Decision tree更快，而且有时候能够获得相近或者更高的准确率
- 但是，决策树的并行实现有几个难点：树的形状是不规则，而且是运行时才确定的， static的分配策略会造成imbalance问题；树的一个node的子node并行执行时，它们需要父节点的部分数据，因此需要processor间data移动，如果数据划分的不够好，poor locality会降低性能
2. Related Work
2.1. Task parallelism
- 将决策树的node分配到不同的processor上
- 缺点是， bad load balance，因为不同processor处理的树的大小是不一致的
2.2. Data parallelism
- 将训练数据划分到不同的processor上，划分策略有水平划分和垂直划分
- 垂直划分，一个processor处理训练数据的一部分属性。垂直划分还是有load imbalance的问题，因为连续属性与离散属性相比，需要更多的计算
- 水平划分，将数据平均划分到processor上。需要在不同processor间通信以获得最佳的split；对每个属性，建立独立的value list；每个node进行split时，在不同processor之间有很高的通信负担
2.3. Hybrid parallelism
- 同时使用Task parallelism和Data parallelism
3. C4.5 parallel implementation
- 水平划分策略，与SLIQ (SPRINT: A scalable parallel classifier for data mining)类似
- 连续属性的lists，根据属性的值，进行全局的sorting
- C4.5的limitation：对连续属性，每个node反复地sort训练examples
- 并行tree构建过程主要是两个问题：split和找到最佳的split
- 每个processor统计本地数据的每个属性的分布情况，然后发送给其他的processor；最佳split找到后，创建child node，相应地划分数据
- 为每个属性建立独立的list，这样能够避免每次evaluate一个连续属性时都要重复排序
- SPRINT避免保存class list，把属性list扩展其他两个fields，训练数据的class label和global index
