[SciPy-User] Finding closest point in array - inverse of KDTree

[Ant]

@Daπid
Thank you! This indeed is twice as fast as doing it normally (not counting the fixed time of sorting A, of course).
I would still like to speed it up, getting another 2x  speedup. This is my code, please tell me if you have any suggestions!

*Preprocessing part* #it can be slow, it is not repeated
indices_sort = np.argsort(A)
sortedA = A[indices_sort]
inv_indices_sort = np.argsort(indices_sort)

*Repeated part
midpoints = k[:-1] + np.diff(k)/2
idx_aux = np.searchsorted(sortedA, midpoints)
idx = []
count = 0
final_indices = np.zeros(sortedA.shape, dtype=int)
old_obj = None
for obj in idx_aux:
   if obj != old_obj:
       idx.append((obj, count))
       old_obj = obj
   count += 1
old_idx = 0
for idx_A, idx_k in idx:
   final_indices[old_idx:idx_A] = idx_k
   old_idx = idx_A
final_indices[old_idx:] = len(k)-1
indicesClosest = final_indices[inv_idx_sort]

Thank you!
@Xavier
Thank you for your answer, but won’t spatial distance be too slow? If it computes the distances from every point of A to every point of k it is computing a lot of unnecessary things.
@Robert
Thank you for the link! Do you think that it will offer signifiant advantages over the search sorted solution? I ask because I have never written anything in Cython (I wouldn’t know where to start, to be fair) so I am a little reluctant to start messing with scipy internal code :)




On 12 Oct 2017, 01:26 +0200, Robert Kern <robert.kern at gmail.com>, wrote:
> On Wed, Oct 11, 2017 at 10:01 AM, Ant <antoniy.py at gmail.com> wrote:
> >
> > Hello all,
> >
> > I have the same question I posted on stack overflow: https://stackoverflow.com/questions/46693557/finding-closest-point-in-array-inverse-of-kdtree
> >
> > I have a very large ndarray A, and a sorted list of points k (a small list, about 30 points).
> >
> > For every element of A, I want to determine the closest element in the list of points k, together with the index. So something like:
> >
> >     >>> A = np.asarray([3, 4, 5, 6])
> >     >>> k = np.asarray([4.1, 3])
> >     >>> values, indices
> >     [3, 4.1, 4.1, 4.1], [1, 0, 0, 0]
> >
> > Now, the problem is that A is very very large. So I can't do something inefficient like adding one dimension to A, take the abs difference to k, and then take the minimum of each column.
> >
> > For now I have been using np.searchsorted, as shown in the second answer here: https://stackoverflow.com/questions/2566412/find-nearest-value-in-numpy-array but even this is too slow.
> >
> > I thought of using scipy.spatial.KDTree:
> >
> >     >>> d = scipy.spatial.KDTree(k)
> >     >>> d.query(A)
> >
> > This turns out to be much slower than the searchsorted solution.
> >
> > On the other hand, the array A is always the same, only k changes. So it would be beneficial to use some auxiliary structure (like a "inverse KDTree") on A, and then query the results on the small array k.
> >
> > Is there something like that?
>
> The KDTree and BallTree implementations in scikit-learn have implementations for querying with other trees. Unfortunately, these implementations are hidden behind an interface that builds the query tree on demand and then throws it away. You'd have to subclass in Cython and expose the `dualtree` implementations as a Python-exposed method.
>
> https://github.com/scikit-learn/scikit-learn/blob/master/sklearn/neighbors/binary_tree.pxi#L1250-L1254
>
> --
> Robert Kern
> _______________________________________________
> SciPy-User mailing list
> SciPy-User at python.org
> https://mail.python.org/mailman/listinfo/scipy-user
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-user/attachments/20171012/e691b700/attachment.html>