[Numpy-discussion] Proposal: scipy.spatial

Anne Archibald peridot.faceted at gmail.com
Tue Sep 30 18:10:46 EDT 2008


2008/9/30 Gael Varoquaux <gael.varoquaux at normalesup.org>:
> On Tue, Sep 30, 2008 at 05:31:17PM -0400, Anne Archibald wrote:
>> T = KDTree(data)
>
>> distances, indices = T.query(xs) # single nearest neighbor
>
>> distances, indices = T.query(xs, k=10) # ten nearest neighbors
>
>> distances, indices = T.query(xs, k=None, distance_upper_bound=1.0) #
>> all within 1 of x
>
>> What do you think of this interface?
>
> k=None in the third call to T.query seems redundant. It should be
> possible do put some logics so that the call is simply
>
> distances, indices = T.query(xs, distance_upper_bound=1.0)

Well, the problem with this is that you often want to provide a
distance upper bound as well as a number of nearest neighbors. For
example, suppose you are trying to find the point of closest approach
of a path to the set of points stored in a kd-tree. You do the first
query normally, but then since the second point is close to the first,
you can accelerate the search dramatically by providing an upper bound
of the distance from the first point's nearest neighbor to the second
point. With a little luck, this will save ever having to visit much of
the tree.

It is also possible, of course, to provide wrappers to query() that do
just one thing; I had this in mind more for fiddling the output
(returning only the distance to the nearest neighbor, for instance).

Anne



More information about the NumPy-Discussion mailing list