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)

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.

## Robust Euclidean embedding

[github]

Python implementation of the REE subgradient algorithm.