title: top-k in mapreduce when k elements do not fit in memory
body: <p>What would be an efficient MapReduce algorithm to find the top-k elements from a dataset, when k is too big to fit k elements in memory? I am talking about a dataset of millions of elements and k being e.g. 3/4 of them. Imagine that each element has a value and we want to find the k elements with the highest values.</p>
  <p>E.g. data in the form:</p>
  <blockquote>
  <p>e1: 5</p>
  <p>e2: 10</p>
  <p>e3: 7</p>
  <p>e4: 8</p>
  </blockquote>
  <p>Then, the top 2 are e4 and e2 (not caring about their relevant order).</p>
  <p>I have seen <a href="https://stackoverflow.com/a/20583371/2516301">the solution to the problem, when k is small enough</a>, but it does not scale.
  Obviously, using a single reducer, would again not be practical (out of memory error).</p>