The horizontal visibility graph (HVG) representation of a time series is a structured graph whose connectivity properties have been used to study the dynamics of a wide range of nonlinear systems. Applications range from the brain (EEG), the heart (ECG) and the financial markets (bid prices), to the sun (solar intensity readings) and river flows. HVGs have also been extended to image-based pattern recognition. Efficient and scalable online HVG construction is vital to extending HVG-based time series analysis to long, streaming, and distributed real-world time series data.The fastest scalable method for constructing HVGs today is the binary search tree (BST) encoding–decoding algorithm, which is O(n log n) in time series length for balanced data such as noise. However, in practice BST is highly sensitive to the geometric structure of a time series and its performance degrades significantly towards O(n^2) when data possess long term dependencies or when the sample frequency is high, which occur regularly in practice. To avoid these problems we leverage an O(n) ordered rooted tree representation of time series that is (graph) dual to the HVG. We demonstrate that this representation leads to an algorithm for HVG construction that is agnostic with respect to the geometry and auto-correlations of the underlying data. Moreover, it possesses an efficient branch fusion operation for tree merging, leading to the idea of a bipartite HVG introduced in this paper, which allows HVGs for very large time series to be constructed efficiently in parallel.After introducing our method and algorithms for parallel construction of HVGs we report on experimental benchmarks comparing their real-world performance to existing approaches on long time series. On data sampled from fractional Brownian motions, deterministic chaotic systems, brain EEG recordings, and the financial markets, our dual tree algorithms significantly outperform previous methods.
|Title of host publication||2021 IEEE International Conference on Big Data (Big Data)|
|Number of pages||11|
|Publication status||Published - 13 Jan 2022|
|Event||2021 IEEE International Conference on Big Data (Big Data) - |
Duration: 15 Dec 2021 → 18 Dec 2021
|Conference||2021 IEEE International Conference on Big Data (Big Data)|
|Period||15/12/21 → 18/12/21|
Bibliographical note© 2022 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
- time series analysis
- graph algorithms
- big data
- signal processing
- horizontal visibility