Fast, Exact Nearest Neighbor in Arbitrary Dimensions with a Cover Tree

Given only a metric between points, how quickly can the nearest neighbor of a point be found? In the worst case, this time is O(n). When these points happen to obey a dimensionality constraint, more s