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

[Jacob VanderPlas]

Patrick,
I think you're correct that the KD implementation in scipy would have to 
be pretty extensively modified to work with periodic boundary 
conditions.  The new ball tree implementation I've been working on 
(which Emanuele mentioned) would be adaptable to your situation with 
minimal additional code - you could even use it as-is with a periodic 
metric defined in python.

The implementation needs a fair bit of work before it will be ready for 
inclusion in scikit-learn, and I haven't had the time to work on it 
recently, but you can take a look!  Let me know if you have any 
questions on that.
   Jake

Patrick Varilly wrote:
> 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 <mailto: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 list
>>     SciPy-Dev at scipy.org <mailto:SciPy-Dev at scipy.org>
>>     http://mail.scipy.org/mailman/listinfo/scipy-dev
>>           
>
>
>     _______________________________________________
>     SciPy-Dev mailing list
>     SciPy-Dev at scipy.org <mailto:SciPy-Dev at scipy.org>
>     http://mail.scipy.org/mailman/listinfo/scipy-dev
>
>
> ------------------------------------------------------------------------
>
> _______________________________________________
> SciPy-Dev mailing list
> SciPy-Dev at scipy.org
> http://mail.scipy.org/mailman/listinfo/scipy-dev
>