# \[ANN\] kdtree 0.1

**URL:** <https://www.ruby-forum.com/t/ann-kdtree-0-1/177916>\
**Category:** Ruby\
**Created:** [October 26, 2009, 5:52pm UTC](https://www.ruby-forum.com/t/ann-kdtree-0-1/177916 "2009-10-26T17:52:38Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![adamdorsey](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/ed8c4c/32.png) [@adamdorsey](https://www.ruby-forum.com/u/adamdorsey)\
**Post date:** [October 26, 2009, 5:52pm UTC](https://www.ruby-forum.com/t/ann-kdtree-0-1/177916/1 "2009-10-26T17:52:38Z")

</div>

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/](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