Fast online computation of the Q_n estimator with applications to the detection of outliers in data streams

摘要

We present FQN (Fast Q_n), a novel algorithm for online computation of the Q_n scale estimator. The algorithm works in the sliding window model, 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 (ⅰ) is faster, requiring only O(s) time in the worst case where s is the length of the window (ⅱ) its computational complexity does not depend on the input distribution and (ⅲ) it requires less space. To the best of our knowledge, our algorithm is the first that allows online computation of the Q_n scale estimator in worst case time linear in the size of the window. As an example of a possible application, besides its use as a robust measure of statistical dispersion, we show how to use the Q_n estimator for fast detection of outliers in data streams. Extensive experimental results on both synthetic and real datasets confirm the validity of our approach.