Parallel processing for distance-based outlier detection on a multi-core CPU
Junki Oku, Keiichi Tamura, Hajime Kitakami · 2014
Outliers are data objects that are not highly likely to occur. These are unusualness data objects such as errors, fraud data, and rare data. In the last few decades, outlier detection has attracted much attention from researchers, because it is widely used for many different application domains. Distance-based outlier detection, which is a non-parametric approach, identifies unusual data objects in a database, where their distance to neighbors is used as a measure of unusualness. Algorithms for distance-based outlier detection are known for their significant computation time. One of the most successful algorithms for the improvement of the distance-based outlier detection algorithms is Orca, which is based on nested loop with randomization and a simple pruning rule. In this paper, we propose a new parallelization model for the parallel processing of Orca-based outlier detection on a multi-core CPU. The proposed parallelization model utilizes data parallelism and a multi-thread model. In the processing of Orca, we need to share an outlier-score table and a cutoff value for pruning among worker threads. To reduce conflicts on sharing, the proposed parallelization model manages outlier-score tables hierarchically and makes the cache of the cutoff value on each worker thread. The experimental results show that the proposed parallelization model outperforms a conventional parallelization model, which utilizes only the data parallelism without managing outlier-score tables hierarchically.