Re:Mining Time-series with Trillions of Points: Dynamic Time...
by phalina on Monday October 29, 2012 @12:45AM
(#4711151)
Yeah, 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.
Re:Mining Time-series with Trillions of Points: Dynamic Time...
by aufreak3 on Monday October 29, 2012 @09:11AM
(#4712055)
Searching 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.
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)#E...