1. Abstract
- focus on 數(shù)據(jù)挖掘任務(wù)的并行共享內(nèi)存
- 貢獻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的副本
- 獨立地更新自己的副本
- 不需要鎖
- 本地所有數(shù)據(jù)處理完后，merge所有副本的增量
2.2. Buffering
- full replication的空間開銷大
- 為每個consumer線程創(chuàng)建一個buffer，consumer線程將對reduction object的更新存儲在buffer中
- 需要存reduction object中element的指針，也要存reduction function的參數(shù)
- 需要single lock鎖住所有的reduction object
2.3. Full locking
- reduction object中的每個element一個lock
- 問題是很多l(xiāng)ock帶來的開銷大，因此提出了3種優(yōu)化方法
2.4. Fixed locking
- 固定數(shù)量的鎖，數(shù)量是l，element i 的鎖是i mod l
- 因為多個element associate with 同一個鎖，并行度被限制
2.5. Group locking
- 為每個group分配一個鎖來減少鎖的數(shù)量
- 代價是并行度受限
2.6. Optimized full lock
- full lock的主要開銷是在獲取鎖時會cache miss
- 創(chuàng)建結(jié)構(gòu)來同時存儲element和它的鎖
- 這樣使得element和clock在一個cache block的概率增加
3. Related work
3.1. 分布式association mining，分布式關(guān)聯(lián)規(guī)則
- 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，分布式?jīng)Q策樹
- 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. 數(shù)據(jù)挖掘算法的分布式框架
- Mining of association rules in very large databases: A structured parallel approach. 但是focus on分布式內(nèi)存的并行化，I/O需要用戶自己處理
- Strategies for parallel data mining. 挖掘不同分布式算法的并行策略的相似性，本文的不同之處在于提供了中間件來利用這種相似性，同時使得并行應(yīng)用的開發(fā)變得簡單
- OpenMP. 共享內(nèi)存編程的通用標準，但是只支持scalar reduction 變量和少量的簡單reduction操作，因此不適用數(shù)據(jù)挖掘算法。而且目前的OpenMP不支持對disk-resident dataset的高效acceess。
4. Summary
- focus on 數(shù)據(jù)挖掘算法的shared memory parallelization
- 挖掘不同數(shù)據(jù)挖掘任務(wù)的并行算法上的相似性，開發(fā)了一個編程interface。用戶只需要稍微改寫一個sequential code，使用reduction object接口來對reduction object中的element進行更新。
- 6種并行技術(shù)
- 實驗：關(guān)聯(lián)規(guī)則，k-means聚類，k近鄰。full replication的結(jié)果最好。
