What is Red-Black Tree DataStructure?

Photo mosaic, datastructure, process speed up?

• Hello,   Last couple days I have made a http://en.wikipedia.org/wiki/Photographic_mosaic. I kept is pretty basic. I have a DB with pictures and their mean colors. I divide my main picture in to a set number of squares. I’ll calculate the mean of these squares and compare them to my DB the closest match will be placed of this square.   II want to improve this process. -      I’m not comparing with only the mean of the square but I’m going to dive it in to 3 x 3 so my vector changes from 3 to 27 dimensions. -      Also I trying to figure out how to speed up the process. Now I’m comparing all of the vectors with a linear search. I was told to look in to a KD tree but with 27 dimensions I’m not sure it will be faster. Now I have 1000 pictures and I’m looking for the 10 closest matches.

• Answer:

  This question sounds similar to Honestly, at your scale, anything you do should be relatively instantaneous.  A KD tree is probably the "most correct" solution, however.  I'm partially talking out of my butt here, but one other thing you might need to be concerned about is the "Curse of Dimensionality."  As the number of dimensions increases, the probability of finding a match "close" to any query point in all dimensions exponentially decreases.  While your method is likely to produce high quality results with a much (much, much, much) higher sample size.than the 1000 pictures you mention above, with only these many it will be rare for you to find the right picture for each of your 3x3 squares.  In fact, I'd wager that you almost never find one that is a very close match.  It could lead to better results if you instead subdivide your main image 3x3 additional times and merely search for matching whole images.  Of course, this could cause you to repeat images, which might be a negative for you, but it will likely lead to a much more properly colored mosaic.