Fast Anomaly Detection for Streaming Data
Swee Chuan Tan, Kai Ming Ting and Tony Fei Liu
This paper introduces Streaming Half-Space-Trees (HS-Trees), a fast one-class anomaly detector for evolving data streams. It requires only labels of normal data, which is useful when anomalous data is rare and not available for training. The model features an ensemble of random HS-Trees, and the tree structure can be constructed without any data. This makes the method highly efficient because it requires no model restructuring when adapting to evolving data streams. Our analysis shows that Streaming HS-Trees has an amortised constant time complexity per example and has a constant memory requirement. When compared with a state-of-the-art method, our method performs favourably in terms of detection accuracy and runtime performance. Finally, our experimental results show that the detection performance of Streaming HS-Trees is not sensitive to its parameter settings.