Online visibility graphs: Encoding visibility in a binary search tree
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 effic...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
American Physical Society
2020-04-01
|
| Series: | Physical Review Research |
| Online Access: | http://doi.org/10.1103/PhysRevResearch.2.023069 |
| _version_ | 1797211484062744576 |
|---|---|
| author | Delia Fano Yela Florian Thalmann Vincenzo Nicosia Dan Stowell Mark Sandler |
| author_facet | Delia Fano Yela Florian Thalmann Vincenzo Nicosia Dan Stowell Mark Sandler |
| author_sort | Delia Fano Yela |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-24T10:27:13Z |
| format | Article |
| id | doaj.art-92e2ab93d3e9467ebcf0a91c8bfd875e |
| institution | Directory Open Access Journal |
| issn | 2643-1564 |
| language | English |
| last_indexed | 2024-04-24T10:27:13Z |
| publishDate | 2020-04-01 |
| publisher | American Physical Society |
| record_format | Article |
| series | Physical Review Research |
| spelling | doaj.art-92e2ab93d3e9467ebcf0a91c8bfd875e2024-04-12T16:52:56ZengAmerican Physical SocietyPhysical Review Research2643-15642020-04-012202306910.1103/PhysRevResearch.2.023069Online visibility graphs: Encoding visibility in a binary search treeDelia Fano YelaFlorian ThalmannVincenzo NicosiaDan StowellMark SandlerA 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.http://doi.org/10.1103/PhysRevResearch.2.023069 |
| spellingShingle | Delia Fano Yela Florian Thalmann Vincenzo Nicosia Dan Stowell Mark Sandler Online visibility graphs: Encoding visibility in a binary search tree Physical Review Research |
| title | Online visibility graphs: Encoding visibility in a binary search tree |
| title_full | Online visibility graphs: Encoding visibility in a binary search tree |
| title_fullStr | Online visibility graphs: Encoding visibility in a binary search tree |
| title_full_unstemmed | Online visibility graphs: Encoding visibility in a binary search tree |
| title_short | Online visibility graphs: Encoding visibility in a binary search tree |
| title_sort | online visibility graphs encoding visibility in a binary search tree |
| url | http://doi.org/10.1103/PhysRevResearch.2.023069 |
| work_keys_str_mv | AT deliafanoyela onlinevisibilitygraphsencodingvisibilityinabinarysearchtree AT florianthalmann onlinevisibilitygraphsencodingvisibilityinabinarysearchtree AT vincenzonicosia onlinevisibilitygraphsencodingvisibilityinabinarysearchtree AT danstowell onlinevisibilitygraphsencodingvisibilityinabinarysearchtree AT marksandler onlinevisibilitygraphsencodingvisibilityinabinarysearchtree |