1. Abstract
- focus on 数据挖掘任务的并行共享内存
- 贡献1：并行策略(full replication, buffering, full locking, fixed locking, group locking, optimized full locking)
- 贡献2：编程接口(reduction object)
- 贡献3：性能测试(apriori association mining, k-means clustering, k-nearest classifier)
2. 并行策略
2.1. Full replication
- 每个consumer线程保存一个reduction object的副本
- 独立地更新自己的副本
- 不需要锁
- 本地所有数据处理完后，merge所有副本的增量
2.2. Buffering
- full replication的空间开销大
- 为每个consumer线程创建一个buffer，consumer线程将对reduction object的更新存储在buffer中
- 需要存reduction object中element的指针，也要存reduction function的参数
- 需要single lock锁住所有的reduction object
2.3. Full locking
- reduction object中的每个element一个lock
- 问题是很多lock带来的开销大，因此提出了3种优化方法
2.4. Fixed locking
- 固定数量的锁，数量是l，element i 的锁是i mod l
- 因为多个element associate with 同一个锁，并行度被限制
2.5. Group locking
- 为每个group分配一个锁来减少锁的数量
- 代价是并行度受限
2.6. Optimized full lock
- full lock的主要开销是在获取锁时会cache miss
- 创建结构来同时存储element和它的锁
- 这样使得element和clock在一个cache block的概率增加
3. Related work
3.1. 分布式association mining，分布式关联规则
- Parallel mining of association rules
- Scalable parallel datamining for association rules
- Parallel and distributed association mining: a survey
3.2 分布式K-means clustering
- A data-clustering algorithm on distributed memory multiprocessors
3.3. 分布式Decision tree classifier，分布式决策树
- Clouds: Classification for large or out-of-core datasets
- Efficient parallel classification using dimensional aggregates
- Scalparc: A new scalable and efficient parallel classification algorithm for mining large datasets
- Sprint: A scalable parallel classifier for data mining
- Parallel formulations of decision-tree classification algorithms
3.4. 数据挖掘算法的分布式框架
- Mining of association rules in very large databases: A structured parallel approach. 但是focus on分布式内存的并行化，I/O需要用户自己处理
- Strategies for parallel data mining. 挖掘不同分布式算法的并行策略的相似性，本文的不同之处在于提供了中间件来利用这种相似性，同时使得并行应用的开发变得简单
- OpenMP. 共享内存编程的通用标准，但是只支持scalar reduction 变量和少量的简单reduction操作，因此不适用数据挖掘算法。而且目前的OpenMP不支持对disk-resident dataset的高效acceess。
4. Summary
- focus on 数据挖掘算法的shared memory parallelization
- 挖掘不同数据挖掘任务的并行算法上的相似性，开发了一个编程interface。用户只需要稍微改写一个sequential code，使用reduction object接口来对reduction object中的element进行更新。
- 6种并行技术
- 实验：关联规则，k-means聚类，k近邻。full replication的结果最好。
