Draco Xu
Advisors
Fatemeh Nargesian
Committee Members
Jiebo Luo, Chen Ding
Abstract
A complex network represents the dynamic of systems by the interactions of a set of anomaly time series. A core task to enable network dynamics analysis on large-scale data is the efficient computation and update of the correlation matrix for user-defined time windows on historical and real-time data. We present TSUBASA, an algorithm for efficiently computing the exact pair-wise time-series correlation based on Pearson’s correlation. By pre-computing simple and low-overhead sketches, TSUBASA can efficiently compute exact pair-wise correlations on arbitrary time windows at query time. For real-time data, TSUBASA proposes a fast and incremental way of updating the correlation matrix. We provide a detailed time and space complexity analysis of TSUBASA. Our experiments show that with the same space overhead as a DFT-based approximate solution, TSUBASA has a lower sketching time and is on par with the approximate solution with respect to query time. TSUBASA is at least one order of magnitude faster than a baseline for both historical and real-time data. We demonstrate tsupy, a Python library, which extends Jupyter Notebook as instrumentation for performing climate network construction and analysis at interactive speed. This demonstration focuses on how tsupy enables dynamic network analysis on climate data. We also show how tsupy can be applied to neuro-imaging to understand the functional connectivity between brain regions.
