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

摘要

The optimal k-segments of an ordered dataset of size n consists of k tuples that are obtained by merging consecutive tuples such that a given error metric is minimized. The problem is general and has been studied in various flavors, e.g., piecewise-constant approximation, parsimonious temporal aggregation, and v-optimal histograms. A well-known computation scheme for the optimal k-segments is based on dynamic programming, which computes a k x n error matrix E and a corresponding split point matrix J of the same size. This yields O(n.k) space and O(n(2).k) runtime complexity.