Looking for (very) fast approximate matching of (sub-)timeseriesAsk Question

问题:

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²).

  1. perfect match of two timeseries (gray and orange)
  2. inaccurate new measurement (orange) but still a match
  3. a short new measurement (orange) but still a match
  4. a huge new measurement (orange) but still a match
  5. a new measurement with failures (orange) but still a match

回答1:


The amortized time for DTW is less than O(N)

Doing this at 100,000Hz would be very easy

Look at this video

https://www.youtube.com/watch?v=d_qLzMMuVQg

标签: pattern-matching time-series matching sequences
© 2014 TuiCode, Inc.