From: Adam Doppelt <amd@...>
Date: 2009-10-27T01:52:43+09:00
Subject: [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
-- 
Posted via http://www.ruby-forum.com/.