Comment by mattiasfestin | Hacker News Reader

Comment by mattiasfestin | Hacker News Reader

Parent Full thread

This is a form of compression that is made to preserve chart visual looks, if I understand it right. There is no analysis on how it bias the data with the down sample.

My instinct is the algorithm looks too specialized for this one task (which is good sometimes, if used for the right task).

As a thought could you not use a FFT to the frequency domain and remove the high frequency data. And then retransform it back to the time domain.

Fourier transforms are used all over the place, and FFT libs are usually well optimized and can even be hardware accelerated.

Without checking it, the cut off frequency would be determined by the Nyquist–Shannon sampling theorem. And should be dependent of the width of the graph in pixels.

So if the graph is resized, then recompute the new down sampled timeseries from the new Nyquist–Shannon sampling limit of the new width.

A sliding DFT can also be used for streaming data for realtime.

You've just described in very basic terms how linear downsampling works (filter -> decimate). It's orders of magnitude more expensive than what is described in the paper, and a crappy sinc interpolator (equivalent to zeroing FFT bins) is not going to be much improvement over the nonlinear approaches described - either objectively in terms of signal degradation due to ripple effects or subjectively, as the paper has explored.

Specifically, this is trying to downsample a chart while only using points from the original time series. Something like an FFT would generate a new series of points which would most likely not be in the original dataset, though they might visually represent them well.

Why not just use a low-pass linear-phase FIR filter instead of FFT/iFFT? Same result but achieved in time-domain, somewhat more performant.

That depends on the filter order. Evaluating a FIR is O(N M^2) where N is the number of data points and M is the size of the FIR. Doing the same with an FFT is O(N Mlog(M)).

Neither is particularly "performant." FFTs and FIRs are big guns!

Would FFT even be appropriate for nonstationary time series? Wavelets seem more appropriate for such time series (not sure about how peformant they would be though, the R package runs pretty slow even for small datasets)

Reply on news.ycombinator.com