Unfortunately, I am not even sure of the keywords to use for this question, so if this has already been asked please point me the right way.
Given a set of vectors:
[3, 5, 3] [10, 23, 5] [123, 53, 97]
(here, 'vector' means one dimensional sets of numeric values).
I'd like to know a way of finding the closest match for any input vector. For example,
[2, 4, 5]
Would return the first one from my list as the closest match. I'd also like to know the distance of the match.
A way of visualising this is like a line graph.
I don't want to linear search. I could have millions of vectors. I do not mind performing pre-processing time; it's search time I want to optimise.
Defining 'closest match'
In this case, let's assume the data is numeric, and the 'closest match' is a simple numeric comparison, giving an absolute distance. For example, comparing
[2, 4, 5] could give distances of the test data of:
[1, 1, 2] [8, 19, 0] [121, 49, 92]
Varying size vectors
How would vectors of different sizes be handled? I'd like to be able to handle cases such as the following input:
Matching the third example from the test data, in some "lower scoring" sense. That's because the two values are similar to the first and last values in the test data, ignoring the middle value, and in order.
Another way of describing it might be - the ordering of the values in the vector is important, but not the position.
I considered some form of clustering - hashing the vectors into buckets, then hashing the input and returning all vectors in the matching bucket. But what troubles me about this is what if a given input is close to the "boundary" of a cluster - other values in adjacent clusters would not be returned, would they?
I want to use this algorithm to find similar musical releases by their constituent track lengths. As such, the lengths can be stored as an integer in some time unit (seconds or milliseconds, say) and the data ends up looking like the above.
So similar to the CDDB (FreeDB) algorithm, but more leniency and the ability to define and explore distance. And support for different length vectors.
Other questions I have looked at
How to find the closest vector to a given vector? seems to discuss 2D points - while this could be considered in a 2D space, the values in each vector must be considered together.