7
$\begingroup$

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]

Improve this question
$\endgroup$
2
  • $\begingroup$ 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... $\endgroup$
    – Richard Arnold Mead
    Commented Oct 30, 2012 at 18:22
  • $\begingroup$ 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). $\endgroup$
    – Vor
    Commented Oct 30, 2012 at 19:25

1 Answer 1

Reset to default
1
$\begingroup$

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} < 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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Your “$y = x_{2n+1}$ ($y = x_{2n}$)” notation is unclear. $\endgroup$
    – James Waldby - jwpat7
    Commented Oct 27, 2012 at 17:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.