Add ASAP Smoothing

[reyjrar]

Paper is https://arxiv.org/pdf/1703.00983.pdf Graphite-api patch is: https://github.com/wyndhblb/graphite_asap Stanford code is: http://futuredata.stanford.edu/asap/#code

Seems like winning.

[dgryski]

This paper, like LTTB, has the issue that it doesn't return evenly spaced points. Some APIs might not like that.

[deniszh]

I think it looks interesting enough to implement that, even with non-evenly spaced points.

[kexinrong]

@dgryski In fact ASAP does return points that are evenly spaced. It dynamically selects a window size for the moving average filter and applies it to the original time series, which does not affect the spacing between points.

Let's say that the original time series contains evenly spaced points, each representing averages of the CPU usage in the past 5 minutes. ASAP might decide that an hourly average better highlights the trend in this time series plot. In this case, ASAP smooths the original time series with a moving average with window size 12, which results in a smoothed time series where each point represents an hourly average but are still 5 minutes apart.

[errx]

btw I've created golang implementation of asap smoothing https://github.com/errx/go-asap