23/08/2020

Ultrafast local outlier detection from a data stream with stationary region skipping

Susik Yoon, Jae-Gil Lee, Byung Suk Lee

Keywords: kernel density estimation, anomaly detection, data stream, local outlier, outlier detection

Abstract Paper Similar Papers

Abstract: Real-time outlier detection from a data stream is an increasingly important problem, especially as sensor-generated data streams abound in many applications owing to the prevalence of IoT and emergence of digital twins. Several density-based approaches have been proposed to address this problem, but arguably none of them is fast enough to meet the performance demand of real applications. This paper is founded upon a novel observation that, in many regions of the data space, data distributions hardly change across window slides. We propose a new algorithm, abbr. STARE, which identifies local regions in which data distributions hardly change and then skips updating the densities in those regions-a notion called stationary region skipping. Two techniques, data distribution approximation and cumulative net-change-based skip, are employed to efficiently and effectively implement the notion. Extensive experiments using synthetic and real data streams as well as a case study show that STARE is several orders of magnitude faster than the existing algorithms while achieving comparable or higher accuracy.

The video of this talk cannot be embedded. You can watch it here:
https://dl.acm.org/doi/10.1145/3394486.3403171#sec-supp
(Link will open in new window)
 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at KDD 2020 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 0
 0
 0
 0
 9:31 
 0
 0
 1
 2
 5:03 
 0
 0
 0
 0
 14:59 
 0
 0
 0
 0
 3:24 
 0
 0
 0
 0
 15:01 
 0
 0
 0
 0
 14:40 
 0
 0
 0
 0
 14:09 
 0
 0
 0
 0
 12:16 
 0
 0
 0
 0
 15:22 
 0
 0
 0
 0
 9:33 
 0
 0
 0
 0
 12:58 
 0
 0
 0
 0
 3:23 
 0
 0
 0
 0
 17:58 
 0
 0
 0
 0
 13:01 
 0
 0
 0
 0
 1:01 
 0
 0
 0
 0
 10:10 
 0
 0
 0
 0
 14:41 
 0
 0
 0
 0
 13:34 
 0
 0
 0
 0
 1:03 
 0
 0
 0
 0
 5:00 
 0
 0
 0
 0
 5:00 
 0
 0
 0
 0
 13:47 
 0
 0
 0
 0
 5:05 
 0
 0
 0
 0
 1:01 
 0
 0
 0
 0
 17:38 
 0
 0
 0
 0
 4:42 
 0
 0
 0
 0
 3:03 
 0
 0
 0
 0
 4:56 
 0
 0
 0
 0
 14:48 
 0
 0
 0
 0
 14:59 
 0
 0
 0
 0
 12:23 
 0
 0
 0
 0
 4:49 
 0
 0
 0
 0
 3:24 
 0
 0
 0
 0
 20:09 
 0
 0
 0
 0
 14:08 
 0
 0
 0
 0
 4:12 
 0
 1
 0
 0
 3:22 
 0
 0
 0
 0
 14:47 
 0
 0
 0
 0
 19:34 
 0
 0
 0
 0
 4:43