[SciPy-Dev] Periodic Boundary Conditions and kd-trees

[Patrick Varilly]

Hi Emanuele,

Thanks for your comments, I will definitely look into cover trees and ball
trees, since these are new to me.  As an aside, though, "distance to the
minimum image" satisfies the triangle inequality, since its the natural
metric for points on tori (easiest to see for 2D periodic boundary
conditions).  What breaks down is the idea that if you have three points
with x-coordinates x1 < x2 < x3, then d(2,3) < d(1,3) [but d(1,3) <= d(1,2)
+ d(2,3) remains true].  This is what might cause trouble with kd-trees,
but my thinking was that if I could phrase all kd-tree operations in terms
of answering the question "what is the minimum distance between x and
region Y of space", then the only difference between PBCs and open boundary
conditions is how you answer that question.

Best,

Patrick

On Thu, Mar 1, 2012 at 4:45 PM, Emanuele Olivetti
<emanuele at relativita.com>wrote:

> **
> Hi Patrick,
>
> The general kd-tree algorithm works for distance functions that are metric
> (e.g. triangle inequality holds). As far as I know the current SciPy
> implementation
> of kd-tree works for Euclidean distance only. There is another similar
> algorithms,
> the BallTree, which is implemented in scikits-learn [0] and it is very
> fast (Cython)
> but again for Euclidean distance only.
> Recently Jake VanderPlas, the author of scikits-learn BallTree started to
> extend it to other distances and set up a templated code for inserting the
> distance
> you like [0]. This might be of interest to you but pay attention to your
> periodic/modulo
> distance because it might not be metric.
>
> Recently I started to extend a pure-Python implementation of the cover-tree
> algorithm which is another very efficient data structure for fast nearest
> neighbor [1].
> The implementation is slow in building the cover-tree - at the moment -
> and very fast during queries but the good thing is that it works for
> general
> metrics. You might be interested in this as well. Unfortunately I am
> swamped in
> other activites so my improvements are very very slow now. It should be
> usable though.
>
> Best,
>
> Emanuele
>
> [0]: https://github.com/jakevdp/pyDistances
> [1]: https://github.com/emanuele/PyCoverTree
>
>
> On 03/01/2012 03:31 PM, Patrick Varilly wrote:
>
> Hi,
>
> I am writing to ask for some guidance / advice with modifying SciPy's
> kd-tree code.  I'm writing a Python code with SciPy that deals with a set
> of points in 3D.  For each one of them, I need to list which other points
> are within a distance r.  The trouble is that the points are in a periodic
> box, so "distance between x and y" means "distance between x and closest
> image of y".  Currently, I'm using code that does a dumb O(N^2) brute force
> search, and was about to code up a cell list to replace it (cell lists are
> commonly used for this in molecular dynamics codes).  However, KD-trees
> seem like a much more generally useful structure for this, and SciPy
> already implements kd-trees for open boundary conditions.  Since periodic
> boundary conditions (PBCs) are quite common in most molecular simulation
> and analysis codes, having PBC-aware kd-trees would be useful to a large
> number of users.
>
> I am thinking of modifying scipy.spatial.kdtree to adapt it to periodic
> boundary conditions, and would like to ask if anyone else has done this or
> something similar to it already.  If not, is there any advice that can be
> had on potential problems that can come up that I should know about before
> embarking on this modification?  My goal would be to contribute this change
> back to SciPy, so any advice on what the most SciPythonic way of exposing
> PBCs in the kd-tree interface would also be welcome.
>
> Thanks,
>
> Patrick
>
>
> _______________________________________________
> SciPy-Dev mailing listSciPy-Dev at scipy.orghttp://mail.scipy.org/mailman/listinfo/scipy-dev
>
>
>
> _______________________________________________
> SciPy-Dev mailing list
> SciPy-Dev at scipy.org
> http://mail.scipy.org/mailman/listinfo/scipy-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20120301/2baf5ff9/attachment.html>