Ultrafast Local Outlier Detection from a Data Stream with Stationary Region Skipping

Susik Yoon, Jae-Gil Lee, Byung Suk Lee

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.
BibTeX
@inproceedings{yoon2020ultrafast,
  author = {Susik Yoon and Jae-Gil Lee and Byung Suk Lee},
  title = {{Ultrafast Local Outlier Detection from a Data Stream with Stationary Region Skipping}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2020},
  doi = {10.1145/3394486.3403171},
}

Loading related content...

Figure