A Scalable Linear-Time Algorithm for Horizontal Visibility Graph Construction Over Long Sequences

Colin Stephen

doi:10.1109/BigData52589.2021.9671517

A Scalable Linear-Time Algorithm for Horizontal Visibility Graph Construction Over Long Sequences

Colin Stephen

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding › peer-review

3 Citations (Scopus)

149 Downloads (Pure)

Abstract

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.

Original language	English
Title of host publication	2021 IEEE International Conference on Big Data (Big Data)
Publisher	IEEE
Pages	40-50
Number of pages	11
ISBN (Electronic)	978-1-6654-3902-2
ISBN (Print)	978-1-6654-4599-3
DOIs	https://doi.org/10.1109/BigData52589.2021.9671517
Publication status	Published - 13 Jan 2022
Event	2021 IEEE International Conference on Big Data (Big Data) - Duration: 15 Dec 2021 → 18 Dec 2021

Conference

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.

Keywords

time series analysis
graph algorithms
runtime
big data
signal processing
horizontal visibility

Access to Document

10.1109/BigData52589.2021.9671517

Post-PrintAccepted author manuscript, 1.26 MBLicence: Unspecified

Cite this

@inproceedings{359c0ebff4644c818e50fe6b22ed1421,

title = "A Scalable Linear-Time Algorithm for Horizontal Visibility Graph Construction Over Long Sequences",

abstract = "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.",

keywords = "time series analysis, graph algorithms, runtime, big data, signal processing, horizontal visibility",

author = "Colin Stephen",

note = "{\textcopyright} 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.; 2021 IEEE International Conference on Big Data (Big Data) ; Conference date: 15-12-2021 Through 18-12-2021",

year = "2022",

month = jan,

day = "13",

doi = "10.1109/BigData52589.2021.9671517",

language = "English",

isbn = "978-1-6654-4599-3",

pages = "40--50",

booktitle = "2021 IEEE International Conference on Big Data (Big Data)",

publisher = "IEEE",

address = "United States",

}

TY - GEN

T1 - A Scalable Linear-Time Algorithm for Horizontal Visibility Graph Construction Over Long Sequences

AU - Stephen, Colin

N1 - © 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.

PY - 2022/1/13

Y1 - 2022/1/13

N2 - 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.

AB - 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.

KW - time series analysis

KW - graph algorithms

KW - runtime

KW - big data

KW - signal processing

KW - horizontal visibility

U2 - 10.1109/BigData52589.2021.9671517

DO - 10.1109/BigData52589.2021.9671517

M3 - Conference proceeding

SN - 978-1-6654-4599-3

SP - 40

EP - 50

BT - 2021 IEEE International Conference on Big Data (Big Data)

PB - IEEE

T2 - 2021 IEEE International Conference on Big Data (Big Data)

Y2 - 15 December 2021 through 18 December 2021

ER -

A Scalable Linear-Time Algorithm for Horizontal Visibility Graph Construction Over Long Sequences

Abstract

Conference

Bibliographical note

Keywords

Access to Document

Fingerprint

Cite this