0
$\begingroup$

For n records distributed amongst m processes/nodes (no shared memory) I'd like to accomplish the following for some given ranking criteria

  • find the rth item.
  • find the rth to r+cth items for some constant c (relatively way smaller than n)

The ranking criteria is known in advance so I can keep the records sorted at each node but I CAN NOT control the distribution for example I can't reorganize the records between nodes such that the first n/m records are in node 1 etc...

What algorithm(s) can I use to accomplish this? Any keywords to search for relevant algorithms or link to some paper on such algorithms is appreciated. I feel this is different from the usual unordered selection algorithms because I have the luxury of keeping data sorted at the different nodes.

$\endgroup$

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.