4 ms·
The "time warp" aspect is very interesting. There is another algorithm for computing similarity between time series, which could still be very useful: cross-co
by peripetylabs 14y ago
The "time warp" aspect is very interesting.
There is another algorithm for computing similarity between time series, which could still be very useful: cross-correlation (also called "coherence" in signals processing). Cross-correlation is O(n log n), so it's perfect for big data applications.
An illustration:
http://en.wikipedia.org/wiki/Coherence_(signal_processing)#Example http://en.wikipedia.org/wiki/Coherence_(signal_processing)#E...
- phalina 14y agoYeah, I was thinking the same thing as I read this. If you calculate the cross correlation of two signals by performing a Fourier transform and then multiplying them, it gives you the correlation of the signals at different offsets as well. Maybe it's hard to calculate the FFT of a dataset that doesn't fit in one machine's memory. Been a while since I studied the FFT.
- aufreak3 14y agoSearching using cross correlation is effectively the same as searching using the euclidean distance metric I think, for which also they have a fast implementation. DTW, however, can answer more interesting questions. For example, if you have two performances of a song captured in MIDI, the timing of each note played can vary a little, tempo can fluctuate and sometimes extra notes can also be introduced. DTW can help find the best mapping between two such performances.