Online visibility graphs: Encoding visibility in a binary search tree

Abstract

A visibility algorithm maps time series into complex networks following a simple criterion, and the resulting visibility graphs have recently proven to be a powerful tool for time series analysis. However, their direct computation is time-consuming and rigid, motivating the development of more efficient algorithms. Here we introduce a description of a method to compute visibility graphs online, which is highly efficient, compatible with batchwise progressive updates, and capable of assimilating new data without having to recompute the graph from scratch. We use a binary search tree to encode and store visibility relations, which can be decoded at a later stage into a visibility graph. The proposed encoder/decoder approach offers an online computation solution at no additional computational cost and makes it possible to use visibility graphs for large-scale time series analysis and for applications where online data assimilation is required.