All of my code is available on github.

Random ball cover (RBC) - GPU

[version 0.2.6, readme], Oct 2011. (Original release: August 2010)

The RBC is a simple geometric data structure for fast nearest neighbor search in metric spaces that is provably sensitive to intrinsic dimensionality. Because of its design, the data structure can make use of the power of parallel systems, like GPUs. The slides from the ADMS talk provide a simple overview of the data structure; see my papers (in particular, Accelerating nearest neighbor search on manycore systems) for a more complete, rigorous description.

This is a C and CUDA implementation of the RBC. It builds the data structure and finds nearest neighbors on a (nvidia) GPU. Modern GPUs provide strong nearest neighbor performance even without a data structure; hence the RBC as implemented here improves over a high baseline. In addition to the basic RBC implementation, the code contains fast brute force kernels, and supports k-NN search via efficient sorting networks.

Version 0.2.6 contains a simplified driver, various cleanups, and a few minor bug fixes. See the versions file in the archive or the git repository for the full development history.

Random ball cover - multicore CPU

[version 0.1.1, readme], June 2011. (Original Release: April 2011)

This is a multicore CPU implementation of the approximate and exact nearest neighbor search algorithms based on the RBC. It has been tested on a variety of machines, ranging from a simple dual-core Mac laptop to a 48-core AMD server machine.

The implementation is written in C and parallelized with OpenMP.

Version 0.1.1 is a minor bugfix.

Bregman ball tree (bbtree)

[code, readme], March 2008.

The bbtree is a data structure for fast nearest neighbor retrieval when nearest is measured not using a metric, but with relative entropy (KL-divergence) or another Bregman divergence. See my ICML 2008 paper for more information on this data structure.