Hacker News Reader

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)#E...

View on HN

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.

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.

Reply on news.ycombinator.com