It's easy to come up with a simple distributed algorithms for finding the maximum element in a set (totally ordered): Divide and conquer.

There are a few publications that present algorithms for distributed maximum-finding. The challenge is to pass the fewest messages between nodes.

Does anyone know of algorithms that tackle the same problem for the distributed "n-largest-finding" problem?

A naive solution is a repeated application of a distributed maximum-finding algorithm by successively slicing off the maximums. Another naive solution is to use a distributed sort. These two are probably not even that bad in the extreme cases (very small n, very large n). But how about finding the 10% largest elements (the top decile)?

For reference: There's a question on SO, CUDA: Finding the N largest values of a sparse array, which leads to just using a sort.


Your Answer

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

Browse other questions tagged or ask your own question.