danl
December 3rd, 2006, 09:58 PM
I have two sets of arrays, one which i will call the source set S, and another
set called A. I need to match every array in A to its closest array in S. Closeness is determined by the euclidean distance if you were to consider the arrays to be n-tuple coordinates. The arrays consist of bytes, and contain a few hundred entries.
My first attempt at this problem is the most obvious one. I compared every array in A to every array in S. If S had m amount of elements and A had k amount of elements then that would be m*k comparisons. This algorithm took way to long.
My second attempt was to have every array in S have references to its nearest neighbors. My alogorithm would start at one array and move from neighbor to neighbor till it found an array that was very closes to the desired array. This had some problems because it would sometimes hit a dead end a return a poor choice for a matching array.
I am currently improving this method to prevent the dead end problem and having some luck, but it is getting more complicated then it probably should be.
In my problem S doesn't ever change and I have alot of time to set up S and analyze it, but when I start matching up arrays in A it needs to happen very fast.
If anyone has any ideas that might help my problem then please let me know. A binary tree search or something like that would be perfect, if I could only figure out a good way to build the tree.
set called A. I need to match every array in A to its closest array in S. Closeness is determined by the euclidean distance if you were to consider the arrays to be n-tuple coordinates. The arrays consist of bytes, and contain a few hundred entries.
My first attempt at this problem is the most obvious one. I compared every array in A to every array in S. If S had m amount of elements and A had k amount of elements then that would be m*k comparisons. This algorithm took way to long.
My second attempt was to have every array in S have references to its nearest neighbors. My alogorithm would start at one array and move from neighbor to neighbor till it found an array that was very closes to the desired array. This had some problems because it would sometimes hit a dead end a return a poor choice for a matching array.
I am currently improving this method to prevent the dead end problem and having some luck, but it is getting more complicated then it probably should be.
In my problem S doesn't ever change and I have alot of time to set up S and analyze it, but when I start matching up arrays in A it needs to happen very fast.
If anyone has any ideas that might help my problem then please let me know. A binary tree search or something like that would be perfect, if I could only figure out a good way to build the tree.