7
$\begingroup$

I am using Python, and I have a Pandas dataframe with hundreds of thousands, if not millions, of $(x,y,z)$ coordinates. I am looking to find an efficient method to index the original dataframe so that I'm only left with entries that are within some distance of a given point $P$ that's not necessarily in the set of coordinates.

The trivial, but surely most expensive, method is to construct a vector between each $(x,y,z)$ point and the point $P$, take the norm, and only keep those that are within the cutoff distance. For millions of points though, as I have to do it dozens of times, this seems terribly inefficient.

What are optimal but still somewhat intuitive methods to do this?

$\endgroup$
  • 2
    $\begingroup$ A very simple modification which will speed up the calculation is to use the square of the norm, which will allow you to avoid calculating the square root of each distance. You might also get some speed up by initially filtering out any point which lies outside a cube. $\endgroup$ – andrew.punnett Mar 25 '18 at 6:23
  • $\begingroup$ There are different norms; some may be easier to calculate than others. It looks like you have in mind the Euclidean norm ||r||=sqrt(x^2+y^2+z^2). But maybe the overall algorithm would be fine using a norm like this ||r||=abs(x)+abs(y)+abs(z)? I.e. locating points within a certain size cube, not sphere centered at a given location. $\endgroup$ – Maxim Umansky Mar 26 '18 at 3:43
  • $\begingroup$ Not in python but asked similar question long time back. scicomp.stackexchange.com/questions/5534/… $\endgroup$ – Kaustubh Kaluskar Mar 27 '18 at 14:55
9
$\begingroup$

You can use Morton keying to sort the coordinate locations by binning them into cubes of some specified size $d$. This is an $\mathcal{O}(N\log N)$ operation. Then, given any point P, you can use its Morton key to search only in a small number $(\mathcal{O}(1))$ of nearby boxes, bounded by your distance criterion. The search for each box is $\mathcal{O}(\log N)$.

$\endgroup$
  • 2
    $\begingroup$ Using the same idea and consuming a bit more memory, you can actually improve the query time for finding a box to $O(1)$ by binning the data in a uniform grid and storing the boxes in a hash table (assuming that the data is spatially sparse enough to make a dense grid a bad approach). $\endgroup$ – Tyler Olsen Mar 24 '18 at 21:24
4
$\begingroup$

You can use any data structure for nearest neighbor search; there are many possibilities, with different tradeoffs. You can trade off space vs query time vs how efficiently you can update the data structure with new points. Specifically, your problem is fixed-radius near neighbor search. Most data structures for nearest neighbor search support this kind of query.

$\endgroup$
  • $\begingroup$ Thank you. This will help with looking at how to best go about this. That being said, I tried what I thought was the "slow" approach and it's extremely fast as implemented in panas/numpy even for millions of points: np.sqrt(np.square(df[['x','y','z']]-P).sum(axis=1)). I then index the original dataframe using this. I'll see how this scales though. $\endgroup$ – Argon Mar 25 '18 at 0:37
  • $\begingroup$ I have successfully used ANN on such data sets in C. I think several python bindings do exist for this library. $\endgroup$ – Bort Mar 26 '18 at 8:32

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.