Fast Detection of Outliers in Data Streams with the Q_n Estimator
share
We present FQN (Fast Q_n), a novel algorithm for fast detection of outliers in data streams. The algorithm works in the sliding window model, checking if an item is an outlier by cleverly computing the Q_n scale estimator in the current window. We thoroughly compare our algorithm for online Q_n with the state of the art competing algorithm by Nunkesser et al, and show that FQN (i) is faster, (ii) its computational complexity does not depend on the input distribution and (iii) it requires less space. Extensive experimental results on synthetic datasets confirm the validity of our approach.
READ FULL TEXT