[SciPy-User] efficient computation of point cloud nearest neighbors

[Anne Archibald]

On 31 May 2011 11:27, Sturla Molden <sturla at molden.no> wrote:
> Den 30.05.2011 20:20, skrev Anne Archibald:
>> If this is not fast enough, it might be worth trying a two-tree query
>> - that is, putting both the query points and the potential neighbours
>> in kd-trees. Then there's an algorithm that saves a lot of tree
>> traversal by using the spatial structure of the query points. (In this
>> case the two trees are even the same.) Such an algorithm is even
>> implemented, but unfortunately only in the pure python KDTree. If the
>> OP really needs this to be fast, then the best thing to do would
>> probably be to port KDTree.query_tree to cython. The algorithm is a
>> little messy but not too complicated.
>
> In this case we just need one kd-tree. Instead of starting from the
> root, we begin with the leaf containing the query point and work our way
> downwards. We then find a better branching point from which to start
> than the root. That is not messy at all :-)

But we can sometimes do better - all the leaves in a leaf node will
have very similar neighbour sets, for example, so in principle one can
avoid traversing (part of) the tree once for each. I'm not sure how
much speedup is really possible, though; since there are kn neighbours
to be listed, you're never going to beat O(kn), and the simple
query-everything approach is only O(kn log n) or so.

> Another thing to note is that making the kd-tree is very fast whereas
> searching it is slow. So using multiprocessing is an option.

cKDTrees cannot currently be copied, but it would be simple to
implement. This would save a bit of time when multiprocessing. That
said, they are also immutable, so multiple threads/processes can
happily operate on the same one.

Anne

> Sturla
> _______________________________________________
> SciPy-User mailing list
> SciPy-User at scipy.org
> http://mail.scipy.org/mailman/listinfo/scipy-user
>