Streaming anomaly detection using randomized matrix sketching
Authors:
Open Access
- 1 November 2015
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 9 (3) , 192-203
Abstract
Data is continuously being generated from sources such as machines, network traffic, application logs, etc. Timely and accurate detection of anomalies in massive data streams has important applications such as in preventing machine failures, intrusion detection, and dynamic load balancing. In this paper, we introduce a novel (unsupervised) anomaly detection framework which can be used to detect anomalies in a streaming fashion by making only one pass over the data while utilizing limited storage. We adapt ideas from matrix sketching to maintain, in a streaming model, a set of few orthogonal vectors that form a good approximate basis for all the observed data. Using this constructed orthogonal basis, anomalies in new incoming data are detected based on a simple reconstruction error test. We theoretically prove that our algorithm compares favorably with an offline approach based on expensive global singular value decomposition (SVD) updates. Additionally, we apply ideas from randomized low-rank matrix approximations to further speedup the algorithm. The experimental results show the effectiveness and efficiency of our approach over other popular scalable anomaly detection approaches.Keywords
This publication has 26 references indexed in Scilit:
- Change-point detection in time-series data by relative density-ratio estimationNeural Networks, 2013
- Low-rank incremental methods for computing dominant singular subspacesLinear Algebra and its Applications, 2012
- Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix DecompositionsSIAM Review, 2011
- Statistical outlier detection using direct density ratio estimationKnowledge and Information Systems, 2010
- Anomaly detectionACM Computing Surveys, 2009
- KDD-Cup 2004ACM SIGKDD Explorations Newsletter, 2004
- Novelty detection: a review—part 1: statistical approachesSignal Processing, 2003
- LOFACM SIGMOD Record, 2000
- Sequential Karhunen-Loeve basis extraction and its application to imagesIEEE Transactions on Image Processing, 2000
- Finding repeated elementsScience of Computer Programming, 1982