Fast Distributed Correlation Discovery Over Streaming Time-Series Data

The dramatic rise of time-series data in a variety of contexts, such as social networks, mobile sensing, data centre monitoring, etc., has fuelled interest in obtaining real-time insights from such data using distributed stream processing systems. One such extremely valuable insight is the discovery of correlations in real-time from large-scale time-series data. A key challenge in discovering correlations is that the number of time-series pairs that have to be analyzed grows quadratically in the number of time-series, giving rise to a quadratic increase in both computation cost and communication cost between the cluster nodes in a distributed environment. To tackle the challenge, we propose a framework called AEGIS. AEGIS exploits well-established statistical properties to dramatically prune the number of time-series pairs that have to be evaluated for detecting interesting correlations. Our extensive experimental evaluations on real and synthetic datasets establish the efficacy of AEGIS over baselines.

Fast Correlation Discovery for Large-Scale Streaming Time-Series Data

Karl Aberer, Tian Guo, Saket Sathe

The dramatic rise of streaming time-series data produced in a vari- ety of contexts, such as stock markets, mobile sensing, sensor net- works, data centre monitoring, etc., has fuelled the development of large-scale distributed real-time computation systems ( e.g., Apache Storm, Spark Streaming, S4, etc.). However, it is still unclear how certain important tasks, which can be performed with relative ease in a centralized system, could be performed using such distributed systems. In this paper, we focus on one such task of continu- ously discovering correlations among a large number of stream- ing time series. While doing so, we address two key challenges: (1) the number of time-series pairs that have to be analyzed grows quadratically (O(n2)) in the number of time-series n, giving rise to a quadratic increase in the communication cost between differ- ent nodes of the distributed system, (2) as the size of the time series grows, the computational and communication costs again increase at a prohibitive rate. To tackle these challenges, we propose an approach referred to as AEGIS. AEGIS approximates a group of streams using afﬁne trans- formations. Then it only communicates these stream groups, which are smaller in size and therefore signiﬁcantly reduces the communi- cation overhead. Secondly, AEGIS dramatically enhances the com- putational efﬁciency by exploiting the properties of afﬁne transfor- mations to prune the number of evaluated correlations. As for base- lines we adapt well-known centralized correlation computation ap- proaches to the distributed environment. Our extensive experimen- tal evaluations on real and synthetic datasets establish that AEGIS outperforms the baseline approaches in terms of communication cost, processing latency, and peak capacity.

2014

Un modèle factoriel dynamique pour séries temporelles

Andrei Zenide

This work deals with factorial models for multiple time series. Its core content puts it at the interface between statistics and finance. After a brief description of the historical link between the two sciences, it reviews the literature on factorial models that are close to the model introduced in this work called The dynamical factor analysis model for time series. This model makes the hypothesis that the observed time series are influenced by a common factor, difficult to define and impossible to measure. No a priori structure is put on the factor, at each point time the value of the factor is considered as a new parameter that has to be estimated. As a consequence of this fact, the number of parameters is large and it is not possible to provide the usual asimptotic properties of the estimations by letting the number of periods tend to infi- nity. Asymptotic results in our context have been obtained by increasing the number of time series. The model makes the hypothesis that there is a linear dependence between the time series and the factor with coefficients, that are not constant over time, but rather follow a smooth random walk. This mean that the linear structure of the model is evolving slowly from a period to another. All the information which is not contained in the factor and the coefficients is considered as white noise. Using the normal distribution makes the estimation more easy and opens a toolbox of statistical methods that have been developed for this kind of data. The model is a part of the family of state space models and the Kalman filter is an essential ingredient of our estimator. The effort was concentrated on the elaboration of the structure of the model. Its complexity was constrained by the difficulty of estimation. The final shape of the model does not allow an analytical solution of the optimization problem introduced by the maximum likelihood estimation of the parameters. Numerical solutions have been found and compared with the parameters for simulated data. Some others models have been developed as simpler versions of the dynamical factor model for time series. The case where the factor can be observed has been studied and a new method for the estimation has been provided and compared with the existing methods. A second study considers a latent factor model without noise. Two methods for the estimation of the factor have been provided. The last chapter contains a detailed description of the main statistical tools used during this work. The links with the previous chapters are highlighted followed by comments.

EPFL2004

SigCO: Mining Significant Correlations via a Distributed Real-time Computation Engine

Karl Aberer, Jean Paul Calbimonte Perez, Tian Guo, Hao Zhuang

The dramatic rise of time-series data produced in a variety of contexts, such as stock markets, mobile sensing, sensor networks, data centre monitoring, etc., has fuelled the development of large-scale distributed real-time computation systems (e.g., Apache Storm, Samza, Spark Streaming, S4, etc.). However, it is still unclear how certain time series mining tasks could be performed using such new emerging systems. In this paper, we focus on the task of efficiently discovering statistically significant correlations among a large number of time series via a distributed realtime computation engine. We propose a framework referred to as SigCO. In SigCO, we put forward a novel partition-aware data shuffling, which is able to adaptively shuffle time series data only to the relevant nodes of the distributed real-time computation engine. On the other hand, in SigCO we design a δ-hypercube structure based correlation computation approach which is capable of pruning unnecessary correlation computations. Finally, our extensive experimental evaluations on real and synthetic datasets establish that SigCO outperforms the baseline approaches in terms of diverse performance metrics.

2015

Un modèle factoriel dynamique pour séries temporelles

Andrei Zenide

EPFL2004