Graph plotting: only keeping most relevant data

In order to save bandwith and so as to not to have generate pictures/graphs ourselves I plan on using Google's charting API:

http://code.google.com/apis/chart/

which works by simply issuing a (potentially long) GET (or a POST) and then Google generate and serve the graph themselves.

As of now I've got graphs made of about two thousands entries and I'd like to trim this down to some arbitrary number of entries (e.g. by keeping only 50% of the original entries, or 10% of the original entries).

How can I decide which entries I should keep so as to have my new graph the closest to the original graph?

Is this some kind of curve-fitting problem?

Note that I know开发者_如何学编程 that I can do POST to Google's chart API with up to 16K of data and this may be enough for my needs, but I'm still curious

---

The flot-downsample plugin for the Flot JavaScript graphing library could do what you are looking for, up to a point.

The purpose is to try retain the visual characteristics of the original line using considerably fewer data points.

The research behind this algorithm is documented in the author's thesis.

Note that it doesn't work for any kind of series, and won't give meaningful results when you want a downsampling factor beyond 10, in my experience.

The problem is that it cuts the series in windows of equal sizes then keep one point per window. Since you may have denser data in some windows than others the result is not necessarily optimal. But it's efficient (runs in linear time).

---

What you are looking to do is known as downsampling or decimation. Essentially you filter the data and then drop N - 1 out of every N samples (decimation or down-sampling by factor of N). A crude filter is just taking a local moving average. E.g. if you want to decimate by a factor of N = 10 then replace every 10 points by the average of those 10 points.

Note that with the above scheme you may lose some high frequency data from your plot (since you are effectively low pass filtering the data) - if it's important to see short term variability then an alternative approach is to plot every N points as a single vertical bar which represents the range (i.e. min..max) of those N points.

---

Graph (time series data) summarization is a very hard problem. It's like deciding, in a text, what is the "relevant" part to keep in an automatic summarization of it. I suggest you use one of the most respected libraries for finding "patterns of interest" in time series data by Eamonn Keogh