Data stream anomaly detection through principal subspace tracking

Abstract

We consider the problem of anomaly detection in multiple co-evolving data streams. In this paper, we introduce FRAHST (Fast Rank-Adaptive row-Householder Subspace Tracking). It automatically learns the principal subspace from N numerical data streams and an anomaly is indicated by a change in the number of latent variables. Our technique provides state-of-the-art estimates for the subspace basis and has a true dominant complexity of only 5Nr operations while satisfying all desirable streaming constraints. FRAHST successfully detects subtle anomalous patterns and when compared against four other anomaly detection techniques, it is the only with a consistent F1 ≥ 80% in the Abilene datasets as well as in the ISP datasets introduced in this work.