Implementation of the Ramer-Douglas-Peucker Algorithm for reducing data points without losing fidelity

[gefaila]

Proposal: Provide a function to implement the RDP algorithm found here or the advanced derivatives listed here

Current behavior: The only way to reduce data points are with the standard aggregate functions (min, max, mean, mode, first, last). There are a number of significant problems for reducing timeseries data with these algorithms

• mean is destructive; i.e. it replaces existing data with averages that never actually occured
• They smooth out outliers, peaks, troughs and points of maximum acceleration that for troubleshooting are usually of most interest to us.
• It's not possible to reconstruct removed data points based on the reduced data set

Desired behavior:

• We have tested the RDP algorithm in python to show that we can easily get 10% compression ratios
• The algorithm retains the spikes, peaks and troughs, accelerations and outliers of interest
• It is possible to guess where the removed points were by interpolating between the filtered data set
• The filtered points are unchanged (they don't have new values or timestamps) so they represent actual values that happened (unlike mean where new points are created that never actually happened).
• We need a simple compression parameter to either fix the number of points compressed to, or fix the error between the original and compressed data sets. ie two versions of the algorithm
  1. Compress this data and give me X points that represent it most faithfully OR
  2. Compress this data and give me the minimum points such that the maximum error to any original point is Y

Alternatives considered: all existing aggregate functions in InfluxDB

Use case: Any industrial IoT use case where data compression is as important as NOT losing key features of the data.

[gefaila]

Note that the RDP algorithm is iterative and so it's unlikely that it can be written in Flux.

[nathanielc]

@gefaila Thanks for this issue, I took a quick look at the algorithm and the request makes a lot of sense. This will be possible to implement in Flux and will be most efficient if implemented in Flux as opposed to doing so in the UI. I'll move this issue to the flux repo and present it to the team.

[gefaila]

Thanks @nathanielc , I'm really excited about this because it's crucial to a whole level of functionality where we integrate our InfluxDB with a dashboard that is very limited on the number of points it can display.

Do you have an ETA, weeks?, months? years? Q2 2022? :-)

[nathanielc]

Most likely months. We plan to start on this in about a month and then I expect it will take a few weeks to actually build. Obviously this timeline is subject to change, but this is the current plan.

[nathanielc]

Another request for something similar using this algorithm has come in https://pkg.go.dev/github.com/dgryski/go-lttb. Maybe we can investigate both? See https://github.com/influxdata/flux/issues/4787

[gefaila]

Another request for something similar using this algorithm has come in https://pkg.go.dev/github.com/dgryski/go-lttb. Maybe we can investigate both? See #4787

I think customers would need both because they excel in slightly different ways:

• RDP needs to be done on the completed data set. The algorithm aims for a line that represents a complete data set to the tolerance that a user sets. RDP cannot be done "on the fly" as data points come in.
• Swinging door is designed to work "live" or as points come in.

Clearly, algorithms that can see all the data before compressing are going to have some advantages over algorithms that only know current and historical data. Our choice was RDP. Swinging door wouldn't do as good a job on retaining the actual features in the data we value.

[nathanielc]

The RDP algorithm has been implemented see https://github.com/influxdata/flux/pull/5078 Closing this issue, the Largest Triangle Three Buckets algo issue will remain open and we can add it alongside RDP once its done.

[nathanielc]

Link to RDP docs https://docs.influxdata.com/flux/v0.x/stdlib/experimental/polyline/rdp/

[gefaila]

This is great ! I have been looking forward to having this for a while! Excellent. Thanks for taking a look and implementing it!

[nathanielc]

@gefaila Glad to hear it, let us know how it works out for you. I have been using it personally to great success as well.