1
$\begingroup$

I am doing time series comparisons. I have a set of values (my query set Q) that I need to compare against many other reference sets (R), each of which contains the same number of values as my query set. Both the query set and the reference sets are normalised using the z score so that reference sets on different scales can be compared against the query set. I will most likely be measuring similarity using Euclidean distance.

The problem I am trying to overcome is the speed with which I can filter through the reference sets to quickly discard those that do not bear enough similarity to my query set. All of the reference sets are loaded into memory prior to running any matching logic so it would be possible for me to run pre-processing / store additional information for each of the reference sets.

My original approach was not using normalised data but only the raw values. This allowed me to just: a) sum the query values b) sum each set of reference values (pre-processed) c) calculate the % difference between the query sum and reference sum and discard any reference sets where the % difference in Sums was over a given threshhold. d) for all the remaining reference sets, compare the % difference of each point (e.g. Q1 vs R1, Q2 vs R2, Q3 vs R3) and average these differences over the set to get an average similarity.

Now that I am normalising the data, the sum of both query and reference sets always equals zero, so I need an alternative method to pre-filter / screen. For example, would it be possible to calculate the Euclidean distance incrementally for the first n values in the set and if it reaches a particular level discard the set entirely? However I wouldn't know where to start in terms of an appropriate cut-off level or how many data points should be included in pre-filtering.

Many thanks.

$\endgroup$
  • $\begingroup$ Could you perhaps do some training on a (relatively small) subsample of your data (the training set)? You would try out a number of cut-off levels and different numbers of data points to include in pre-filtering, and then find which combination gives the best results in another (relatively small) subsample (the validation set)? This will not guarantee you good results for (the rest of) the whole sample but at least could be a step forward. $\endgroup$ – Richard Hardy Jan 13 '15 at 14:49
  • $\begingroup$ Regarding your original approach that you had to abandon due to normalization: perhaps you could instead calculate the sum of squares of (1) query values and (2) the reference values and (3) calculate the % distance between the two. $\endgroup$ – Richard Hardy Jan 13 '15 at 14:53
  • $\begingroup$ Sorry for the delay in replying and thank you for the suggestion. I ended up using the Keogh lower bound model of dynamic time warping: cs.ucr.edu/~eamonn/LB_Keogh.htm $\endgroup$ – Myk Jan 29 '15 at 21:32

Your Answer

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

Browse other questions tagged or ask your own question.