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.