Visibility graphs: a data streaming approach

Abstract

RESUMEN: El presente trabajo de tesis está dedicado al desarrollo de una comparativa entre algunos de los métodos existentes para computar el grafo de visibilidad de una serie de tiempo bajo condiciones convencionales y en su implementación en tiempo real, así como a la propuesta de una metodología que pretende eficientar el cómputo del grafo en su implementación en tiempo real. La comparativa realizada para los algoritmos abarca diferentes condiciones y fue implementada utilizando series de tiempo sintéticas y de datos reales. Los datos sintéticos están compuestos por series de tiempo aleatorias; es decir, ruido blanco, series de tiempo de ruido browniano y series de tiempo de ruido browniano fraccional, mientras que las series de tiempo reales abarcan diferentes fenómenos como lo son series de latido cardíaco, series de tiempo financieras y sísmicas. Los algoritmos puestos a prueba fueron: el algoritmo original, el algoritmo ordenar y vencer y el algoritmo propuesto. El análisis fue realizado en diferentes condiciones, comenzando por un análisis en condiciones normales; es decir, cuando la serie de tiempo está definida y se computa un único grafo de visibilidad. Análisis en condiciones en las que es necesaria la actualización parcial del grafo, por ejemplo, ante una ventana deslizante y adición de nodos individuales. La sensibilidad del algoritmo fue puesta a prueba generando variaciones en diferentes propiedades intrínsecas de las series de tiempo como lo son la distribución de los datos y la correlación existente entre ellos, así como la periodicidad de las series de tiempo para observar la robustez del método ante estos parámetros. La comparativa realizada en las diferentes condiciones hizo posible observar que el algoritmo propuesto muestra una ventaja en el cómputo del grafo de visibilidad para series de tiempo sintéticas y reales con respecto a los otros algoritmos cuando las condiciones del estudio son en tiempo real o empleando una ventana deslizante.

ABSTRACT: This thesis presents the development of a comparison between some of the reported methods for calculating the visibility graph of a time-series, under regular scenarios and under a streaming implementation. Also outlines the design of a novel method that enhance the computation time of the visibility graph under streaming conditions. The test was made for various algorithms and it encompasses several conditions. It was built up for particular time-series, both synthetic and real ones. The synthetic data was formed of a random series or white noise, Brownian noise time-series and fractional Brownian noise time-series. Meanwhile, the real data was formed of time-series from different natures, covering heart-beat, financial and seismic time- series. Algorithms under review are: a modification of the original approach, the sort and conquer algorithm and the proposed method. The sensitivity of the designed algorithm was tested by changing some intrinsic properties of the time-series like the distribution of the data, the correlation between the data points and the periodicity of the time-series to test the fitness of the proposed algorithm to these parameters. The results of the comparison under the different conditions revealed that the proposed algorithm presents an improvement in computation time, when measuring the visibility graph for synthetic data and real time-series, in comparison with the analyzed algorithms under streaming conditions or when running a sliding window.