Replace KDTree library with alternative

[kain88-de]

Is there something against switching the KDTree library?

Currently you are using a pretty old C implementation. It would for example be possible
to use the scikit-learn KDTree.

[hainm]

what's wrong with 'old'?

[richardjgowers]

There's also scipy.spatial.KDTree which wouldn't introduce a new dependency

So I guess things to prove would be

• benchmarks of 250,000 3d coordinates, both creating the Tree and querying it
• checking all methods have a counterpart (same functionality)

The other thing is all we currently use KDTree for is distance based selections I think... And the downside with it is it doesn't handle PBC. So a better solution might be to introduce a capped distance search method (using domain decomposition into cells). I was playing around with making one last month, https://github.com/richardjgowers/cellgrid

This would also be awesome for lots of common stuff in very large systems

[kain88-de]

It's SWIG interface currently doesn't support Python3. scikit-learn would support py2 and py3. I also have good experience with it's performance. It would also mean one less thing which has to be maintained.

[kain88-de]

@richardjgowers what would you suggest is a good test system?

[richardjgowers]

Timeit in ipython is good enough, and we can assume that particles are randomly space, so something like...

import numpy as np
from scipy import spatial
from MDAnalysis.lib import KDTree

coords = np.random.random(750000).reshape(250000, 3).astype(np.float32)

t = KDTree.KDTree(3, 10)
%timeit t.set_coords(coords)

%timeit t2 = spatial.KDTree(coords)

I get this:

In [13]: %timeit t.set_coords(coords)
1 loops, best of 3: 833 ms per loop

In [16]: %timeit t2 = spatial.KDTree(coords)
1 loops, best of 3: 805 ms per loop

I think the setup cost of the KDTree will be the largest cost, but it's also worth checking that all methods are available in the replacement. We don't directly use the KDTree, but wrap it in a MDAnalysis.lib.KDTree.NeighbourSearch.

[kain88-de]

http://nbviewer.ipython.org/gist/kain88-de/3617d6ec20aaf3cb1ef4

It looks like the sklearn implementation is a lot faster then the one from scipy.

[richardjgowers]

Hmm ok, and the sklearn KDTree has 96%+ test coverage and supports py3.

For fairness the mda kdtree search was 2x as fast, so after 700,000 searches it's quicker :D

Ok, if you can rewrite NeighborSearch to use the sklearn kdtree then this should be ok unless there's something I've mussed

[orbeckst]

One reason for bundling KDTree was that we didn't really like introducing scipy or sklearn as hard dependencies for core MDAnalysis because in the past this was awful to just pip install.

By default, KDTree is only used for the around selection; point uses distance_matrix if I remember correctly. However, building manual KDTree selections has been pretty useful.

Issue #137 was looking at an implementation of KDTree with PBC.

[richardjgowers]

Re: #137, I don't think there's a way to add PBC at the C level. My best solution to that was to add too many coordinates to the KDTree (replicate the images), and this is done outside of the KDTree. So having our own KDTree doesn't affect the issue

[kain88-de]

I'm just porting the selection object to use the sklearn KDTree. Some of the tests are failing right now. But just seeing that the tests in test_analysis:TestHydrogenBondingAnalysisChecking fail doesn't tell me much what the problem is due to the test design. It is not even that easy to figure out that the test
does exactly.

[mnmelo]

I hit a similar test failure in my half-way cleanup of the selection module (I left that on stand-by pending the development of the new AtomGroup model and use of pyparsing; see #371).

I had reflowed much of the point and around code, to reduce duplication, and was not surprised I broke something. But now you find a failure in the same tests. Maybe

1. Those are the only tests that really use the KDTree feature, and both our fixes are indeed borked; or
2. That module has a bug somewhere.

I'm not sure which I prefer to be true...

Here's my test error log (notice that something else also fails for test_atomgroup.py).
Let me know if you'd like me to upload my half-done branch.