I'm dealing with a huge database of timeseries. A value is saved every n milliseconds. A new timeseries must be checked against old timeseries already in the DB.
At this moment I'm stucked as every solution is expensive like O(n²).
Below I have some pictures, showing short timeseries (gray and orange) which are a match. The algorithm should be able to identify such matches without beeing to accurate as I need speed. A approximation would be enough.
I've studied some paper out in the net dealing with "longest common subsequence problem" or "Dynamic time warping". But either dealing with perfect measurements or perfect sizes or beeing O(n²).
The amortized time for DTW is less than O(N)
Doing this at 100,000Hz would be very easy
Look at this video