Abstract: With the advent of big data era,outlier detection has attracted extensive attention.Computational resources of the traditional K-nearest neighbor outlier detection dealing with massive high dimensional data with single machine are insufficient,and the MapReduce in Hadoop cannot effectively deal with frequent iteration calculation problem.According to the above problems,this paper put forward a Spark-based parallel outlier detection algorithm of K-nearest neighbor,named SPKNN.Firstly,in the stage of map,the algorithm tries to find the local K nearest neighbors for each partition of the data in all data set.Then in the reduce stage,it determines the global K nearest neighbors according to the local K nearest neighbors of each partition.Finally,it calculates the degrees of outliers by using global K nearest neighbors and select outliers.Compared with the traditional K-nearest neighbor outlier detection,the performance of the SPKNN has an approximate linear relationship with computing resources in the premise of ensuring the detection accuracy.And compared with other outlier detection methods,it doesn’t need additional extension data,support iteration calculation and can reduce I/O costs by using memory cache.Experiment results of SPKNN show that it has high efficiency and scalability for massive data sets.

Key words: K-nearest neighbors, Outlier detection, Parallel, Spark