Let's say I have two vectors A and B, of lengths, m, and n respectively. They are not "signals" but a collection of ordered time marks or indexes from another two "original" longer vectors (let's call them X and Y).
I try to compare A and B to "estimate" the similarity between X and Y. If they are aligned I can use a simple Jaccard index to do it. However, X and Y (and so A and B) can be delayed and/or steched with each other. I've assumed that if X and Y are similar, then B should be a linear function of A (B = c*A+d, c and d scalars). Besides, some elements could not match exactly or be missing in the other vector because A and B are of different lengths. For instance:
A = [1 6 12 25 36 37 40], B = [3 13 25 73 82]
Should match the following pairs:
C = [[1,3],[6,13],[12,25],[36,73],[40,82]] -> B = 2*A+1
What algorithm or method can I use to find the gain c and offset d to get the best alignment between A and B? In other words, the parameters that maximize the amount of common elements between both these vectors.
Typically A,B are around 150 elements, and 0.8 < c < 1.2.

A little context: I'm trying to make a song dedupe application in C#. In fact, X and Y are audio firngerprints (chromaprints) made with AcousticID, which are basically binary matrixes (every row is a 32-bit integer). This questions could be directly solved to align X and Y but I think it could be harder due to the "noisy" nature of the prints (sample) and the larger size of vectors.

  • $\begingroup$ This might help. Although it does not already include stretching. But this is something you should be able to incorporate. $\endgroup$
    – Nico Schertler
    Jul 28 '18 at 5:34
  • $\begingroup$ See dsp.stackexchange.com/questions/736/… $\endgroup$ Sep 29 '18 at 7:46

The most similar method to your thought is finding a "linear regression". Hence, you can use a c# library or code to compute "linear regression" for the points of in A|B elements pairs.

  • $\begingroup$ Yes, that was my first idea, but the usual method I know (Linear Least Squares) require the vectors to be the same length. Is there another method? $\endgroup$
    – adrianjgp
    Jul 28 '18 at 16:32

I believe that what you want is the DTW (Dynamic Time Warping) algorithm. There are several implementation options. Here's one that might suit your needs:


You can also check the FAST DTW algorithm.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy