A
Adam Doppelt
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
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