Cargando…

Teaching Ordinal Patterns to a Computer: Efficient Encoding Algorithms Based on the Lehmer Code

Ordinal patterns are the common basis of various techniques used in the study of dynamical systems and nonlinear time series analysis. The present article focusses on the computational problem of turning time series into sequences of ordinal patterns. In a first step, a numerical encoding scheme for...

Descripción completa

Detalles Bibliográficos
Autores principales: Berger, Sebastian, Kravtsiv, Andrii, Schneider, Gerhard, Jordan, Denis
Formato: Online Artículo Texto
Lenguaje:English
Publicado: MDPI 2019
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7514243/
http://dx.doi.org/10.3390/e21101023
_version_ 1783586543186739200
author Berger, Sebastian
Kravtsiv, Andrii
Schneider, Gerhard
Jordan, Denis
author_facet Berger, Sebastian
Kravtsiv, Andrii
Schneider, Gerhard
Jordan, Denis
author_sort Berger, Sebastian
collection PubMed
description Ordinal patterns are the common basis of various techniques used in the study of dynamical systems and nonlinear time series analysis. The present article focusses on the computational problem of turning time series into sequences of ordinal patterns. In a first step, a numerical encoding scheme for ordinal patterns is proposed. Utilising the classical Lehmer code, it enumerates ordinal patterns by consecutive non-negative integers, starting from zero. This compact representation considerably simplifies working with ordinal patterns in the digital domain. Subsequently, three algorithms for the efficient extraction of ordinal patterns from time series are discussed, including previously published approaches that can be adapted to the Lehmer code. The respective strengths and weaknesses of those algorithms are discussed, and further substantiated by benchmark results. One of the algorithms stands out in terms of scalability: its run-time increases linearly with both the pattern order and the sequence length, while its memory footprint is practically negligible. These properties enable the study of high-dimensional pattern spaces at low computational cost. In summary, the tools described herein may improve the efficiency of virtually any ordinal pattern-based analysis method, among them quantitative measures like permutation entropy and symbolic transfer entropy, but also techniques like forbidden pattern identification. Moreover, the concepts presented may allow for putting ideas into practice that up to now had been hindered by computational burden. To enable smooth evaluation, a function library written in the C programming language, as well as language bindings and native implementations for various numerical computation environments are provided in the supplements.
format Online
Article
Text
id pubmed-7514243
institution National Center for Biotechnology Information
language English
publishDate 2019
publisher MDPI
record_format MEDLINE/PubMed
spelling pubmed-75142432020-11-09 Teaching Ordinal Patterns to a Computer: Efficient Encoding Algorithms Based on the Lehmer Code Berger, Sebastian Kravtsiv, Andrii Schneider, Gerhard Jordan, Denis Entropy (Basel) Article Ordinal patterns are the common basis of various techniques used in the study of dynamical systems and nonlinear time series analysis. The present article focusses on the computational problem of turning time series into sequences of ordinal patterns. In a first step, a numerical encoding scheme for ordinal patterns is proposed. Utilising the classical Lehmer code, it enumerates ordinal patterns by consecutive non-negative integers, starting from zero. This compact representation considerably simplifies working with ordinal patterns in the digital domain. Subsequently, three algorithms for the efficient extraction of ordinal patterns from time series are discussed, including previously published approaches that can be adapted to the Lehmer code. The respective strengths and weaknesses of those algorithms are discussed, and further substantiated by benchmark results. One of the algorithms stands out in terms of scalability: its run-time increases linearly with both the pattern order and the sequence length, while its memory footprint is practically negligible. These properties enable the study of high-dimensional pattern spaces at low computational cost. In summary, the tools described herein may improve the efficiency of virtually any ordinal pattern-based analysis method, among them quantitative measures like permutation entropy and symbolic transfer entropy, but also techniques like forbidden pattern identification. Moreover, the concepts presented may allow for putting ideas into practice that up to now had been hindered by computational burden. To enable smooth evaluation, a function library written in the C programming language, as well as language bindings and native implementations for various numerical computation environments are provided in the supplements. MDPI 2019-10-21 /pmc/articles/PMC7514243/ http://dx.doi.org/10.3390/e21101023 Text en © 2019 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).
spellingShingle Article
Berger, Sebastian
Kravtsiv, Andrii
Schneider, Gerhard
Jordan, Denis
Teaching Ordinal Patterns to a Computer: Efficient Encoding Algorithms Based on the Lehmer Code
title Teaching Ordinal Patterns to a Computer: Efficient Encoding Algorithms Based on the Lehmer Code
title_full Teaching Ordinal Patterns to a Computer: Efficient Encoding Algorithms Based on the Lehmer Code
title_fullStr Teaching Ordinal Patterns to a Computer: Efficient Encoding Algorithms Based on the Lehmer Code
title_full_unstemmed Teaching Ordinal Patterns to a Computer: Efficient Encoding Algorithms Based on the Lehmer Code
title_short Teaching Ordinal Patterns to a Computer: Efficient Encoding Algorithms Based on the Lehmer Code
title_sort teaching ordinal patterns to a computer: efficient encoding algorithms based on the lehmer code
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7514243/
http://dx.doi.org/10.3390/e21101023
work_keys_str_mv AT bergersebastian teachingordinalpatternstoacomputerefficientencodingalgorithmsbasedonthelehmercode
AT kravtsivandrii teachingordinalpatternstoacomputerefficientencodingalgorithmsbasedonthelehmercode
AT schneidergerhard teachingordinalpatternstoacomputerefficientencodingalgorithmsbasedonthelehmercode
AT jordandenis teachingordinalpatternstoacomputerefficientencodingalgorithmsbasedonthelehmercode