A Fast Search Algorithm of Anomaly in Data Streams Based on Shifted Wavelet Tree

Author

Kong, Ying-hui ; Lv, Yun-jie ; Yuan, Jin-sha ; Liu, Yan-ming

Author_Institution

Dept. of Electron. & Commun. Eng., North China Electr. Power Univ., Baoding

Volume

4

fYear

2008

fDate

12-14 Dec. 2008

Firstpage

627

Lastpage

630

Abstract

Anomaly detection is to find aggregate which is different from the most aggregates. Aiming at the limitation of the anomaly detection algorithm of shifted wavelet tree (SWT) in data streams, we propose the improved algorithm which constructs the monotonic search space for binary search after removing the disturbance of bumps to increase the efficiency of detection, and uses the real-time incremental update algorithm for meeting the requirement of the online processing of the data streams. The simulation experiments using two data sets of the Gamma Ray and the Power Quality Disturbance (PQD) verify the high effectiveness and accuracy of our algorithm.

Keywords

data analysis; tree searching; anomaly detection; binary search; data streams anomaly; fast search algorithm; gamma ray; monotonic search space; online processing; power quality disturbance; real-time incremental update algorithm; shifted wavelet tree; Aggregates; Algorithm design and analysis; Computer science; Data engineering; Data structures; Detection algorithms; Power engineering and energy; Software algorithms; Software engineering; Tree data structures; anomaly detection; binary search; data streams; incremental update; shifted wavelet tree;

fLanguage

English

Publisher

ieee

Conference_Titel

Computer Science and Software Engineering, 2008 International Conference on

Conference_Location

Wuhan, Hubei

Print_ISBN

978-0-7695-3336-0

Type

conf

DOI

10.1109/CSSE.2008.841

Filename

4722697