On 27 Jun 2008, at 3:11 am, Andrew Wagner wrote: For what it's worth, a 3-dimensional kd tree really flew on this problem.
I did some reading up on this, and it seems interesting. It would be need to implement something like this in Haskell, but I can't seem to find any detailed specs on the data-structure. Got any recommendations?
http://en.wikipedia.org/wiki/K-d_tree is perhaps the obvious place to start. There's a link there to Jon L. Bentley's original (1975) paper, which is really very clear. The key to getting an efficient version in C was to specialise the code to the particular k that I wanted (k=3). Of course there are much newer data structures that can do all sorts of things, but for simply finding the closest point in 1, 2, 3, or 4-dimensional space k-d trees are darned good. There isn't much that works well for high dimensions. Last year I marked a 4th year project that studied/evaluated a comparatively recent data structure that was said to be good for high dimensions. I had difficulty understanding it, because I couldn't see where the recursive step was. The answer was that there wasn't one: the algorithm worked better for high dimensions than other trees because it turned into a simple linear search after one partitioning step. In effect, it was too dumb to keep tripping over its own feet. So _really_ don't expect k-d trees to work well for large k.