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.


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.