title: Search for all nearest neighbors within a certain radius of a point in 3D?
body: <p>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.</p>
  
  <p>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.</p>
  
  <p>My question is:</p>
  
  <ul>
  <li>Is there any better way or a better data structure than Kd-trees in this case?
  <ul>
  <li>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.</li>
  </ul></li>
  </ul>
  
  <p>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.</p>