[ANN] kdtree 0.1

I’ve written a fast 2d kdtree gem. kdtree was specifically created to
solve the nearest neighbor problem for Urbanspoon across nearly 1
million restaurants. Here are some benchmarks for a tree with 1 million
nodes on my dev machine:

build - 10.5s
nearest point - 0.000009s
nearest 5 points - 0.000011s
nearest 50 points - 0.000031s
nearest 255 points - 0.000140s

You can download the gem and read the accompanying blog post here:

http://gurge.com/blog/2009/10/22/ruby-nearest-neighbor-fast-kdtree-gem/

Features
######################

  • very fast
  • can be written to disk and read later to avoid build step
  • uses a minimal amount of memory
  • tested on Mac/Linux w/ Ruby 1.8.5-1.8.7
  • MIT license

Anti-features
######################

  • no editing after the tree is built
  • not thread safe, uses static memory
  • allocates a single block for the whole tree (20 bytes per node)
  • limited to returning 255 results

This is my first shot at a ruby gem, please be gentle. Feedback welcome.
Thanks,

Adam

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

| Privacy Policy | Terms of Service | Remote Ruby Jobs