Statistical monitoring of thousands of data streams in real time

Consider the problem of monitoring tens of thousands of time series data streams in an online fashion and making decisions based on them. In addition to single stream statis-tics such as average and standard deviation, we also want to nd high correlations among all pairs of streams. A stock market trader might use such a tool to spot arbitrage oppor-tunities. This paper proposes eÆcient meth-ods for solving this problem based on Discrete Fourier Transforms and a three level time in-terval hierarchy. Extensive experiments on synthetic data and real world nancial trad-ing data show that our algorithm beats the di-rect computation approach by several orders of magnitude. It also improves on previous Fourier Transform approaches by allowing the eÆcient computation of time-delayed correla-tion over any size sliding window and any time delay. Correlation also lends itself to an eÆ-cient grid-based data structure. The result is the rst algorithm that we know of to compute correlations over thousands of data streams in real time. The algorithm is incremental, has xed response time, and can monitor the pair-wise correlations of 10,000 streams on a single PC. The algorithm is embarrassingly paral-lelizable