FROD: Fast and Robust Distance-Based Outlier Detection with Active-Inliers-Patterns in Data Streams

The detection of distance-based outliers from streaming data is critical for modern applications ranging from telecommunications to cybersecurity. However, existing works mainly concentrate on improving the responding speed, none of these proposals can perform well in streams with varying data distribution. In this paper, we propose a Fast and Robust Outlier Detection method (FROD in short) to solve this dilemma and achieve the promotion in both detection performance and processing throughput. Specifically, to adapt the changing distribution in data streams, we employ the Active-Inliers-Pattern which dynamically selects reserved objects for further outlier analysis. Moreover, an effective micro-cluster-based data storing structure is proposed to improve the detection efficiency, which is supported by our theoretical analysis on the complexity bounds. Moreover, we present a potential background updating optimization approach to hide the updating time. Experiments performed on real-world and synthetic datasets verify our theoretical study and demonstrate that our algorithm is not only faster than state-of-the-art methods, but also achieve a better detection performance when the outlier rate fluctuates.