I need to solve a very large O(10^10) linear selection problem in a distributed memory machine, is there any library that will solve it for me?

In shared memory machines, e.g. std::nth_element does it in average O(n) but deterministic O(n) algorithms also exist. I could live with something worse as long as it's easy to implement. I would also prefer for it to work on input iterator/input ranges than to have linear complexity in order to save memory. I have a dataset that I want to postprocess and then use as input to the linear selection algorithm, it would be better if I could do it "on the fly". I also only want to solve the linear selection problem for certain values, and wouldn't care to solve it multiple times, once for each value.

  • $\begingroup$ Can you give us an order of magnitude for $n$? $\endgroup$
    – Bill Barth
    Mar 26 '13 at 20:37
  • $\begingroup$ The baseline algorithm to beat would be a short-circuited distributed-memory sort. You would be paying at extra $\log n$ factor though. $\endgroup$ Mar 26 '13 at 22:23
  • $\begingroup$ @BillBarth the order is O(10^10). $\endgroup$
    – gnzlbg
    Mar 27 '13 at 7:52
  • $\begingroup$ @JackPoulson for the sort do I need to have all my values in memory? The point is that input iterators/ranges are one-way passes (you can't go back). However if I need to have everything in memory I can construct a random-access range from the input range. $\endgroup$
    – gnzlbg
    Mar 27 '13 at 7:55
  • $\begingroup$ Do you mean that each process would have a one-way iterator which allows for traversal over a subset of the list? $\endgroup$ Mar 27 '13 at 13:33

I think you want to take a look at section 5.1 of this one of my papers: http://www.math.tamu.edu/~bangerth/publications/2010-distributed.pdf

The algorithm described there has complexity $O\left(\frac NP \log_2 P\right)$. The code has only some 20 lines.


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.