Ultrafast Local Outlier Detection from a Data Stream with Stationary Region Skipping
Lists
Only you see this
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...