GreedyTree

There are many interesting and complex data structures for doing proximity search such as nearest neighbor search. This one is designed as a simple hybrid between the sb data structure of Ken Clarkson and Covertrees by Beygelzimer et al.

The main advantage over previous structures is its profound simplicity. Another side interest is that it doesn’t require logarithms because there are no explicit levels in the tree.

class GreedyTree(M, seed=None, scaling=inf)

The GreedyTree encodes a tree of points. If the points are ordered according to the greedy permutation, the child of a point is its nearest predecessor in the ordering.

ann(q, eps=0)

Return a (1+eps)-approximate nearest neighbor to q.

nn(q)

Return the nearest neighbor of q in the GreedyTree.

rangecount(center, radius, slack=0)

Count the points in the ball with the given center and radius.

If the slack is nonzero then the count could include some points within distance radius + slack of the center.