Search for all nearest neighbors within a certain radius of a point in 3D?

Question

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.

Karlsbad

An efficient implementation in C++ can build kd-trees for ~10 mio points in a few seconds. std::nth_element is very efficient for getting the median (linear complexity on average). A second crucial point for efficiency is to allocate all tree nodes at once (in advance as an array). – Sackman

@Sackman thanks, can you suggest some links to similar implementations of Kdtrees preferably in C++ – Karlsbad