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

[Emanuele Olivetti]

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
> 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/ba882b06/attachment.html>