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

    Research output: Chapter in Book/Report/Conference proceedingConference proceedingpeer-review

    13 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 languageEnglish
    Title of host publication2021 IEEE International Conference on Big Data (Big Data)
    PublisherIEEE
    Pages40-50
    Number of pages11
    ISBN (Electronic)978-1-6654-3902-2
    ISBN (Print)978-1-6654-4599-3
    DOIs
    Publication statusPublished - 13 Jan 2022
    Event2021 IEEE International Conference on Big Data (Big Data) -
    Duration: 15 Dec 202118 Dec 2021

    Conference

    Conference2021 IEEE International Conference on Big Data (Big Data)
    Period15/12/2118/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

    Fingerprint

    Dive into the research topics of 'A Scalable Linear-Time Algorithm for Horizontal Visibility Graph Construction Over Long Sequences'. Together they form a unique fingerprint.

    Cite this