6
$\begingroup$

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 and SO

$\endgroup$
  • $\begingroup$ Do you need parallel because of multicore, GPU, or an actual parallel system ? Have you looked at ANN ? $\endgroup$ – Suresh Venkat Jul 18 '11 at 20:51
  • $\begingroup$ because both. what is ANN? $\endgroup$ – Open the way Jul 18 '11 at 22:08
  • $\begingroup$ simultaneously crossposted on MSE without linking. $\endgroup$ – Kaveh Jul 19 '11 at 4:17
  • $\begingroup$ sorry, I will update the question $\endgroup$ – Open the way Jul 19 '11 at 8:22
  • 1
    $\begingroup$ @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). $\endgroup$ – Kaveh Jul 19 '11 at 13:07
10
$\begingroup$

This is the well-studied problem of 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 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.
$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

Something using octrees, I suspect. If you break space up, then you can farm off subtrees to separate processors.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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