Authors: S. Muthukrishnan, Rahul Shah, Jeffrey Scott Vitter
ABSTRACT
One of the central tasks in managing, monitoring and mining
data streams is that of identifying outliers. There is a long
history of study of various outliers in statistics and databases,
and a recent focus on mining outliers in data streams.
Here, we adopt the notion of ``deviants'' from Jagadish et al \cite{jkm} as outliers. Formally, deviants are defined based on a representation sparsity metric, i.e., deviants are values whose removal from the dataset leads to an improved compressed representation of the
remaining items. Thus, deviants are not global maxima/minima, but rather these are appropriate local aberrations. Deviants are known to be of great mining value in time series databases.
We present first-known algorithms for identifying deviants on
massive data streams. Our algorithms monitor streams using very
small space (polylogarithmic in data size) and are able to
quickly find deviants at any instant, as the data stream evolves over time. For all versions of this problem---uni- vs multivariate
time series, optimal vs near-optimal vs heuristic solutions,
offline vs streaming---our algorithms have the same framework of maintaining a hierarchical set of candidate deviants that are
updated as the time series data gets progressively revealed.
We show experimentally using real network traffic data (SNMP aggregate time series) as well as synthetic data that our algorithm is not only remarkably accurate in determining the deviants, but also that evolution of deviants over time reveals interesting artifacts in data streams.
DIMACS Home Page