# Line smoothing algorithm that perserve data uniformity

Intro:

I'm working with huge data set that i need to plot in browser, and since there may be up to 1M points my idea was to create different representations for different zoom levels

lets say i have 100k points, i would average two-by-two until i get 50k, then i would repeat that until i get below 500 points (my arbitrary threshold)

so on the most zoomed-out level i would draw all 500 points, or part of it, depending of the chart size, and as i zoom in, i would switch to next zoom level (and stream data if user drags selection l/r), and ultimately if user wants to see fine grain details he can zoom to 0 zoom level and see all the fine details.

I actually created this prototype, and its working quite well, except for one thing: side-effect of this is, as you can imagine, that peaks are lost in those iterations of averaging.

I did some research and find about Douglas-Peucker algorithm, and how it can perserve peaks, i did some tests, and it works quite well, but the problem with that is that if it encounters a series of data (y values) [1,1,1,1,5,6,1,1,1,1,1,1] it will smooth that to something like [1,6,1,1] which doesn't work for me since i need to keep ratio of zoom levels like this

n (length of original data) > n/2 > n/4 > n/8 > .....

I read quite few papers on line smoothing, but all algorithms that i found are accepting distance threshold, that they use for smoothing as a parameter, and none of those can accept number of desired output elements, and also, since their goal is to smooth the line, they will transform sequence like this (y values) [1,1,1,1,1,1,1,1,1,1,1] into [1,1]

So, finally, my question:

Is there an algoritm that:

• instead of usual distance threshold accepts the desired number of output elements
• tries to perserve peaks (as Douglas-Peucker does)
• will smooth data uniformly, so even if it gets (y values) [1,1,1,1,1,1] and i say i want 3 outputs, event if it IS in theory correct to smooth as [1,1] i would need to get [1,1,1] instead

Also, please don't be confused by lack of X axis information because it is irrelevant since all data are measured from 1 to n in steps of 1, so there are no N/A values, or blank spots, or values like [1.3,1.4,3]

x is always [1,2,3....n]

-
This sounds very much like an application of self-similarity (as seen with fractals for example) where you would have to programmatically determine the appropriate equation(s) and algorithm(s) based on the full data set, or the perhaps simpler feature preserving image scaling algorithms... –  Richard Arnold Mead Oct 30 '12 at 18:22
Just a curiosity: did you try the trivial algorithm (no average, no smoothing)? If you are at zoomout level $z$ i.e. you want to represent the $n$ original points using only $m = n/2^z$ points; then generate the $m$ values just picking the min and the max of each distinct interval $[i*2n/m,(i+1)*2n/m)$ with $i=0,...,m/2-1$. For example at zoom level 1 reduce the points [1 2 6 9 2 2 3 5] to [1 9 2 5] (1,9 are the min/max of the first 4 points, 2,5 are the min/max of the second 4 points). –  Vor Oct 30 '12 at 19:25

Suggestion 1: Use a linear filter. Instead of computing the average $x_{2n},x_{2n+1} \mapsto (x_{2n}+x_{2n+1})/2$, try averaging over a larger sequence, e.g. $y_n = (x_{2n-1}+2x_{2n}+2x_{2n+1}+x_{2n+2})/6$.
Suggestion 2: Use a conditional filter: if $x_{2n} < x_{2n+1} > x_{2n+2}$ or $x_{2n-1} < x_{2n} > x_{2n+1}$, then let $y = x_{2n+1}$ or $y = x_{2n}$, respectively, and similarly for local minima; otherwise use the average (or a linear filter) as before.
Your “$y = x_{2n+1}$ ($y = x_{2n}$)” notation is unclear. –  jwpat7 Oct 27 '12 at 17:00