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?

Improve this question
$\endgroup$
3
  • 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$
    – andypea
    Mar 25, 2018 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, 2018 at 3:43
  • $\begingroup$ Not in python but asked similar question long time back. scicomp.stackexchange.com/questions/5534/… $\endgroup$
    – Kaustubh Kaluskar
    Mar 27, 2018 at 14:55

2 Answers 2

Reset to default
7
$\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)$.

Improve this answer
$\endgroup$
1
  • 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, 2018 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.

Improve this answer
$\endgroup$
2
  • $\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, 2018 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, 2018 at 8:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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