<p>Something using <a href="http://en.wikipedia.org/wiki/Octree" rel="nofollow">octrees</a>, I suspect.  If you break space up, then you can farm off subtrees to separate processors.</p>

CC BY-SA 3.0
2011-07-19T02:48:40.223Z
2011-07-19T02:48:40.223Z
Peter Boothe
<p>I would personally sort the space along one axis, cut it into overlapping strips.  Sort each strip along a second axis, cut it into overlapping strips.  Then sort those strips along a third axis, cut it into overlapping strips.  Then compare each point in the "on my side of the median of all of the overlaps" to all points in the final box you drew, and sort those.</p>

<p>This is likely to be efficient because you never compute pairwise distances unless the points are, in fact, relatively close to each other.</p>

<p>This is not an explicitly parallel algorithm, but there are a lot of opportunities for parallelism at various points in this algorithm.</p>

CC BY-SA 3.0
2011-07-19T01:18:46.270Z
2011-07-19T01:18:46.270Z
btilly
<p>This is the well-studied problem of <a href="http://en.wikipedia.org/wiki/Nearest_neighbour_search">Nearest Neighbour Search</a>.  There is not one 'best solution' to the problem---you'll want to choose trade offs based on the input and requirements.</p>

<p>Do you need the creation of the data structure to be parallel?  Or just the queries?  Depending on how many thousands of points you're talking about, if your set of points is static it might not be impractical to do something naive like:</p>

<ul>
<li>For each point $x$, construct a list of all other points, sorted by distance from $x$.</li>
</ul>

<p>This can be done in $O(n^2\log n)$ time and $O(n^2)$ space, which is not that bad if you only need to run it once for a set of several thousand points.  It will give you constant or logarithmic query time for pretty much anything you'd want to do.</p>

<p>If you need something smarter that requires less space or less time, I'd recommend reading the Wikipedia article on <a href="http://en.wikipedia.org/wiki/Nearest_neighbour_search">Nearest Neighbour Search</a> and perhaps refining your question, telling us </p>

<ul>
<li>how many times you'll need to build the structure from scratch</li>
<li>whether or not it needs to be dynamic</li>
<li>what exactly needs to be parallelized</li>
<li>whether your 'cutoff value' for Euclidean distance is fixed, or will vary from query to query</li>
<li>if possible, a tighter estimate on the number of points.  When somebody says 'thousands' sometimes they mean 3,000 and sometimes they mean 300,000.</li>
</ul>

CC BY-SA 3.0
2011-07-19T13:17:07.243Z
2011-07-19T13:17:07.243Z
James King
<p>Given a collection of thousands of points in 3D, I need to get the list of neighbours for each particle that fall inside some cutoff value (in terms of euclidean distance), and if possible, sorted from nearest fo farthest.</p>

<p>Which is the fastest parallel algorithm for this purpose? </p>

<p>PS: I also crossposted this <a href="https://math.stackexchange.com/questions/52202/best-algorithm-for-calculating-lists-of-neighbours">in math exchange</a> and SO</p>

CC BY-SA 3.0
2011-07-18T20:51:21.600Z
Do you need parallel because of multicore, GPU, or an actual parallel system ? Have you looked at ANN ?
Suresh Venkat
CC BY-SA 3.0
2011-07-18T22:08:57.690Z
because both. what is ANN?
Open the way
CC BY-SA 3.0
2011-07-19T04:17:55.673Z
[simultaneously crossposted on MSE](http://math.stackexchange.com/questions/52202/best-algorithm-for-calculating-lists-of-neighbours) without linking.
Kaveh
CC BY-SA 3.0
2011-07-19T08:22:16.183Z
sorry, I will update the question
Open the way
CC BY-SA 3.0
2011-07-19T13:07:57.743Z
@flow: simultaneously cross-posting is discouraged, it divides the answers and comments between sites. Next time please wait a few days to see if you get an answer to your question on the first site and if you don't get a satisfying answer then post it on the other site (improving it based on any answers on the first site and why the answers were not satisfactory for you).
Kaveh
CC BY-SA 3.0
2011-07-19T14:19:35.903Z
ok, thanks for the advice, I will proceed that way the next time
Open the way
CC BY-SA 3.0
2011-07-21T05:10:12.167Z
ANN is a package for near neighbor search from Dave Mount at UMD
Suresh Venkat
<graph-algorithms><big-list><dc.parallel-comp><near-neighbors>
Best algorithm for calculating lists of neighbours
Open the way
# Best algorithm for calculating lists of neighbours

(Asked by: username_0 on 2011-07-18)

Given a collection of thousands of points in 3D, I need to get the list of neighbours for each particle that fall inside some cutoff value (in terms of euclidean distance), and if possible, sorted from nearest fo farthest.

Which is the fastest parallel algorithm for this purpose?

PS: I also crossposted this [in math exchange](https://math.stackexchange.com/questions/52202/best-algorithm-for-calculating-lists-of-neighbours) and SO

**Tags:** graph-algorithms, big-list, dc.parallel-comp, near-neighbors

> **Comments:**
> **username_1**: Do you need parallel because of multicore, GPU, or an actual parallel system ? Have you looked at ANN ?  
> **username_0**: because both. what is ANN?  
> **username_2**: [simultaneously crossposted on MSE](http://math.stackexchange.com/questions/52202/best-algorithm-for-calculating-lists-of-neighbours) without linking.  
> **username_0**: sorry, I will update the question  
> **username_2**: @flow: simultaneously cross-posting is discouraged, it divides the answers and comments between sites. Next time please wait a few days to see if you get an answer to your question on the first site and if you don't get a satisfying answer then post it on the other site (improving it based on any answers on the first site and why the answers were not satisfactory for you).  
> **username_0**: ok, thanks for the advice, I will proceed that way the next time  
> **username_1**: ANN is a package for near neighbor search from Dave Mount at UMD  

---

## 3 answers

### Answer by username_5 on 2011-07-19. Score: 10 | Accepted answer

This is the well-studied problem of [Nearest Neighbour Search](http://en.wikipedia.org/wiki/Nearest_neighbour_search). There is not one 'best solution' to the problem---you'll want to choose trade offs based on the input and requirements.

Do you need the creation of the data structure to be parallel? Or just the queries? Depending on how many thousands of points you're talking about, if your set of points is static it might not be impractical to do something naive like:

* For each point $x$, construct a list of all other points, sorted by distance from $x$.

This can be done in $O(n^2\log n)$ time and $O(n^2)$ space, which is not that bad if you only need to run it once for a set of several thousand points. It will give you constant or logarithmic query time for pretty much anything you'd want to do.

If you need something smarter that requires less space or less time, I'd recommend reading the Wikipedia article on [Nearest Neighbour Search](http://en.wikipedia.org/wiki/Nearest_neighbour_search) and perhaps refining your question, telling us

* how many times you'll need to build the structure from scratch
* whether or not it needs to be dynamic
* what exactly needs to be parallelized
* whether your 'cutoff value' for Euclidean distance is fixed, or will vary from query to query
* if possible, a tighter estimate on the number of points. When somebody says 'thousands' sometimes they mean 3,000 and sometimes they mean 300,000.


---

### Answer by username_3 on 2011-07-19. Score: 2

Something using [octrees](http://en.wikipedia.org/wiki/Octree), I suspect. If you break space up, then you can farm off subtrees to separate processors.


---

### Answer by username_4 on 2011-07-19. Score: 2

I would personally sort the space along one axis, cut it into overlapping strips. Sort each strip along a second axis, cut it into overlapping strips. Then sort those strips along a third axis, cut it into overlapping strips. Then compare each point in the "on my side of the median of all of the overlaps" to all points in the final box you drew, and sort those.

This is likely to be efficient because you never compute pairwise distances unless the points are, in fact, relatively close to each other.

This is not an explicitly parallel algorithm, but there are a lot of opportunities for parallelism at various points in this algorithm.


---

