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.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe