4
$\begingroup$

I have about 80 million spatial points(3D) and I want to find all the nearest neighbors of a query point which lie under a sphere of a certain radius(can be given as input) with the query point as center.

I have read about some data structures that are used for such kind of search, such as Kd-trees, octrees or range trees. For my application, I only need to populate the data structure once and then search for multiple query points.

My question is:

  • Is there any better way or a better data structure than Kd-trees in this case?
    • With kd trees, I'll have to find the median of such a large dataset multiple times, which may take a lot of time to populate the tree.

I don't know much about any of these data structures so could you please refer some tutorials about whatever solution you may recommend. I know this question may seem repeated but from all the questions I found and read, no one was using such a large set of points.

Improve this question
$\endgroup$
1
  • $\begingroup$ assuming that an approximate median (i.e. an element of rank $(1 \pm \epsilon)n$) works just fine for kd trees, you can sample a much smaller set of points and return the median of the sample $\endgroup$
    – Sasho Nikolov
    Commented Jun 11, 2013 at 16:47

1 Answer 1

Reset to default
8
$\begingroup$

My recommendation is NOT to roll your own for now. There are two software packages that I'd recommend you try first.

  • ANN (by Arya and Mount) is state-of-the-art for low dimensional near neighbor search and includes the "fixed radius" search that you're looking for.
  • Nearpt3 (Wm Randolph Franklin) is another package that is specifically optimized for 3D, and supposedly can handle 100s of millions of points. I'm not entirely sure it handles fixed radius queries as well as regular nearest neighbor search, but you can look into it.

If neither of these is appropriate, then you can return and ask :).

Improve this answer
$\endgroup$

Your Answer

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

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