<div class="gmail_quote">On Sat, Mar 10, 2012 at 8:00 PM, Ralf Gommers <span dir="ltr">&lt;<a href="mailto:ralf.gommers@googlemail.com">ralf.gommers@googlemail.com</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br><br><div class="gmail_quote"><div class="im">On Fri, Mar 9, 2012 at 2:23 AM, Patrick Varilly <span dir="ltr">&lt;<a href="mailto:patvarilly@gmail.com" target="_blank">patvarilly@gmail.com</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">


Dear all,<div><br></div><div>Following up from the conversation with Emanuele Olivetti and Jake VanderPlas, I&#39;ve implemented [0] a drop-in replacement for scipy.spatial.kdtree that uses cover trees instead of kd-trees to answer nearest neighbor queries in a general metric space.  To me, this is useful for finding nearby particles in a 3D periodic box in the context of molecular simulations, but I&#39;m sure it&#39;s more generally useful.  It addresses the same problem that Jake&#39;s BallTrees code addresses in scikit-learn, but I&#39;ve done my best to reproduce the API of scipy.spatial.kdtree in order to make this code mostly painless to use.  In particular, kd-tree&#39;s useful function for finding all the points in one tree that are neighbors of every point in another tree (ironically, &quot;query_ball_tree&quot;) is also implemented here for cover trees.  I modified kdtree&#39;s extensive unit test to use cover trees, and the code passes it.</div>

</blockquote><div> </div></div><div>Out of interest, are you planning to propose this for inclusion in scipy or scikit-learn once it&#39;s done, or keep it as a standalone package?<br></div></div></blockquote><div><br></div>
<div>Eventually, I&#39;d like to propose it for inclusion in scipy, since this functionality is not exclusive to machine learning.  I&#39;m using it for molecular simulations, and didn&#39;t even know that nearest-neighbor queries were useful in machine learning!  I would never have though of looking in scikit-learn for this.  But I would like to address the two outstanding issues (vectorized distances and Cython implementation) before proposing it for inclusion.  On that same vein, I don&#39;t know why BallTree is in scikit-learn and not scipy, for the same reasons.</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="gmail_quote"><div class="im"><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div>This is definitely work in progress, and its performance could certainly be improved.  But since it may already be useful to others, I&#39;d like to put it out there to get some early feedback.  Two things that it *doesn&#39;t* do yet are use any vectorized form of a distance function (so every distance calculation between two points costs one Python function call), and there&#39;s no speedy Cython version yet.  </div>
</blockquote></div><div><br>Jaakko Luttinen proposed just two days ago to expose the distance functions in scipy/spatial/src/distance.c. That may also be useful for you.<br></div></div></blockquote><div><br></div><div>Thanks, I&#39;ll look into it when I get a chance.</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="gmail_quote"><div class="im"><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div>Finally, in reading carefully through kdtree.py, I found a clear bug in the code, whereby the &quot;eps&quot; parameter for approximate queries doesn&#39;t get forwarded from the externally visible function &quot;query&quot; to the internal function &quot;__query&quot; that does the work.</div>


</blockquote></div><div><br>Could you open a ticket for that with a little more detail? Or if you feel like it, a pull request would be even better:)\<br></div></div></blockquote><div><br></div><div>I sent in a pull request for it.  It&#39;s the first time I do this, so apologies in advance if I somehow screwed it up.</div>
<div><br></div><div>All the best,</div><div><br></div><div>Patrick</div></div>