KD-Trees and MagLev

MagLev KD-Tree Example

A few weeks ago, I came across this blog post by Adam Doppelt from Urbanspoon. In the post, Adam describes how Urbanspoon solved a problem they had managing their data to enable nearest neighbor searches. They need to find the nearest N items to a given location, e.g., find the 10 nearest coffee shops to my current location. It’s an interesting post and I encourage you to read it to see the various solutions they tried and rejected. In the end, they solved their problem by writing a KD-Tree C-extension, which they have published as a RubyGem.

When I read the post, it seemed that the problem was a natural fit for MagLev. So, I implemented a pure ruby version of a KD-Tree and compared it to the kdtree gem and to the pure ruby solution running on MRI 1.8.6 and 1.9.2 ¹.

VM(s) + Repository = MagLev

MagLev is a new Ruby VM with built-in object persistence. GemStone has recently released a public alpha of MagLev.  I’m going to give a quick overview of how the VM and the object Repository work to serve up Ruby objects.