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

<ul>
<li><a href="http://www.cs.umd.edu/~mount/ANN/">ANN</a> (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. </li>
<li><a href="http://www.ecse.rpi.edu/Homepages/wrf/pmwiki/pmwiki.php/Research/Nearpt3">Nearpt3</a> (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. </li>
</ul>

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

CC BY-SA 3.0
2013-06-11T15:50:47.020Z
2013-06-11T15:50:47.020Z
Suresh Venkat
<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>

CC BY-SA 3.0
2013-06-11T16:47:37.370Z
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
Sasho Nikolov
<ds.data-structures>
Search for all nearest neighbors within a certain radius of a point in 3D?
user16368
# Search for all nearest neighbors within a certain radius of a point in 3D?

(Asked by: username_0 on 2013-06-11)

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.

**Tags:** ds.data-structures
> **Comments:**
> **username_1**: 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  

---

## 1 answers

### Answer by username_2 on 2013-06-11. Score: 8 | Accepted answer

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

* [ANN](http://www.cs.umd.edu/~mount/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](http://www.ecse.rpi.edu/Homepages/wrf/pmwiki/pmwiki.php/Research/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 :).


---

