A scalable dynamic programming scheme for the computation of optimal k-segments for ordered data

作者:

Highlights:

• Dynamic programming algorithm for optimal k-segments with improved runtime.

• Split-point graph as replacement for the dynamic programming matrix with small memory footprint.

• Parallelization of the dynamic programming algorithm.

摘要

Highlights •Dynamic programming algorithm for optimal k-segments with improved runtime.•Split-point graph as replacement for the dynamic programming matrix with small memory footprint.•Parallelization of the dynamic programming algorithm.

论文关键词:Optimal k-segments,Dynamic programming,Parsimonious temporal aggregation,Piecewise constant approximation,v-optimal histograms,Data approximation

论文评审过程:Received 15 March 2016, Revised 23 June 2016, Accepted 30 August 2016, Available online 9 September 2016, Version of Record 19 September 2017.

论文官网地址:https://doi.org/10.1016/j.is.2016.08.002