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

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 14
  • Download : 0
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.
Publisher
Association for Computing Machinery
Issue Date
2020-08-25
Language
English
Citation

26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2020, pp.1181 - 1191

DOI
10.1145/3394486.3403171
URI
http://hdl.handle.net/10203/277127
Appears in Collection
CS-Conference Papers(학술회의논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0