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.