Continuous monitoring of distance-based outliers over data streams

• Main Authors: Kontaki, M, Gounaris, A, Papadopoulos, A N, Tsichlas, K, Manolopoulos, Y
• Format: Conference Proceeding
• Language: English
• Subjects: Algorithm design and analysis; Data mining; Data structures; Detection algorithms; Heuristic algorithms; Measurement; Monitoring
• ISSN: 1063-6382; 2375-026X
• DOI: 10.1109/ICDE.2011.5767923

Anomaly detection is considered an important data mining task, aiming at the discovery of elements (also known as outliers) that show significant diversion from the expected case. More specifically, given a set of objects the problem is to return the suspicious objects that deviate significantly from the typical behavior. As in the case of clustering, the application of different criteria lead to different definitions for an outlier. In this work, we focus on distance-based outliers: an object x is an outlier if there are less than k objects lying at distance at most R from x. The problem offers significant challenges when a stream-based environment is considered, where data arrive continuously and outliers must be detected on-the-fly. There are a few research works studying the problem of continuous outlier detection. However, none of these proposals meets the requirements of modern stream-based applications for the following reasons: (i) they demand a significant storage overhead, (ii) their efficiency is limited and (iii) they lack flexibility. In this work, we propose new algorithms for continuous outlier monitoring in data streams, based on sliding windows. Our techniques are able to reduce the required storage overhead, run faster than previously proposed techniques and offer significant flexibility. Experiments performed on real-life as well as synthetic data sets verify our theoretical study.