Vantage Point Trees.

Vantage Point Trees enable fast nearest-neighbor queries in metric spaces

vp-tree

Vantage point trees, as described in

Data structures and algorithms for nearest neighbor search in general metric spaces - P. N. Yianilos

http://web.cs.iastate.edu/~honavar/nndatastructures.pdf

Usage

Import 'Data.VPTree', which also contains usage instructions and comments

Benchmarks

Cumulative memory usage and garbage collection cycles :

$ stack bench -- vp-tree:bench-memory