2009-06-16

fastest kd-tree ever

I spent the day reading and commenting on Dustin Lang's dissertation chapter on the kd-tree. Lang and Mierle have created for the Astrometry.net system the fastest kd-tree ever. The speed-up comes from tricks you can play with static data structures. That is, if you have a data set that changes rarely (or never) and you need to do fast lookup in the data set far more frequently than you need to edit the data set, you can build a static block in memory that contains the data, structured as a hierarchical binary tree, but without any pointer dereferencing or complicated (and therefore expensive and slow) structures. The thesis chapter on this is great, and it will make a great paper. The code is available under the GPLv2 license by request to Lang.

2 comments:

  1. This idea is not new. As far as I know, luxrender's BVH (bounding volume hierarchy) has a similar structure.

    ReplyDelete
  2. Drip: I think that might be because both Lang and luxrender were influenced by Keir Mierle (Google), who is a credited co-author on this chapter of Lang's thesis.

    ReplyDelete