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]
Here are two suggestions for you to try.

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} &lt; x_{2n+1} &gt; x_{2n+2}$ or $x_{2n-1} &lt; x_{2n} &gt; 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.