Acceleration Of LOF Algorithm On GPU

Anomaly detection is to find those deviant ones from behaviors of system or user, which has been used in a wide range of applications such as, credit card fraud detection, network intrusion detection, system fault detection and so on. The method used generally in anomaly detection is to store the normal behavioral characteristics into the database, and then compare the behavior characteristics of current instance and those in the database. If the deviation is large enough, the current instance will be determined as an exception.There are a variety of algorithms for anomaly detection. Among these methods, LOF (Local Outlier Factor) algorithm determines whether certain instance is an anomaly based on its LOF value calculated by the algorithm. LOF algorithm has been widely used for its high detecting efficiency. While, its computational complexity is rather high and the most expensive part of it is kNN (k Nearest Neighbors) problem. The heavy time cost of LOF algorithm has a significant impact to its application which has high demand in low latency when datasets are large-scale. Though there has been lots of work done for the optimization of kNN and LOF algorithms so far, these optimization methods are still subject to high complexity when datasets are large-scale or with high data dimensions, even both.During recent years, GPU has been developed with the integration of hundreds or even thousands of processors and possesses powerful parallel computing capacity. The emergence of unified architecture and CUDA (Compute Unified Device Architecture) facilitates greatly the programming for researchers, which makes the application of GPU extend from the original graphic rendering field to general-purpose computing soon. Among them, there are some studies and optimizations having been done to accelerate kNN and LOF algorithms by parallel based on GPU. However, there are different deficiencies in their work for not making full use of the architecture characteristics of GPU and much more efforts should be made to accelerate LOF and kNN algorithms.The purpose of this paper is to accelerate the LOF algorithm based on GPU and focus on the efficient implementation of kNN algorithm, the most time heavycost of LOF. We divide kNN problem as two steps:distance calculation and k smallest elements finding, and optimize both respectively. For distance calculation phase, we redefine the data structures and store the instances in the way profile to taking advantages of coalesced accessing characteristics of global memory on GPU to enhance memory access efficiency. In phase of finding k smallest elements, we filter the distance values in advance and only a small amount of them will be involved in sorting at last. By this technique, we reduce the time overhead brought by thread serialization. This paper achieves an efficient kNN algorithm on GPU, based on which we also implement the complete LOF algorithm on CPU-GPU heterogeneous platform ultimately.Finally, we make several experimental evaluations on multiple real datasets, and compare them with existed parallel kNN algorithms and LOF algorithm based on GPU. Experimental results show that this paper achieves more markable performance improvement than those existed work so far.