title: Hadoop / MapReduce - Optimizing "Top N" Word Count MapReduce Job
body: <p>I'm working on something similar to the canonical MapReduce example - the word count, but with a twist in that I'm looking to only get the <strong>Top N</strong> results.  </p>
  
  <p>Let's say I have a very large set of text data in HDFS.  There are plenty of examples that show how to build a Hadoop MapReduce job that will provide you with a word count for every word in that text.  For example, if my corpus is:</p>
  
  <blockquote>
    <p>"This is a test of test data and a good one to test this"</p>
  </blockquote>
  
  <p>The result set from the standard MapReduce word count job would be:  </p>
  
  <blockquote>
    <p>test:3, a:2, this:2, is: 1, etc..  </p>
  </blockquote>
  
  <p>But what if I <strong>ONLY</strong> want to get the Top 3 words that were used in my entire set of data?  </p>
  
  <p>I can still run the exact same standard MapReduce word-count job, and then just take the Top 3 results once it is ready and is spitting out the count for EVERY word, but that seems a little inefficient, because a lot of data needs to be moved around during the shuffle phase.</p>
  
  <p>What I'm thinking is that, if this sample is large enough, and the data is well randomly and well distributed in HDFS, that each Mapper does not need to send ALL of its word counts to the Reducers, but rather, only some of the top data.  So if one mapper has this:</p>
  
  <blockquote>
    <p>a:8234, the: 5422, man: 4352, ......  <em>many more words</em> ...  , rareword: 1, weirdword: 1, etc.</p>
  </blockquote>
  
  <p>Then what I'd like to do is only send the Top 100 or so words from each Mapper to the Reducer phase - since there is very little chance that "rareword" will suddenly end up in the Top 3 when all is said and done.  This seems like it would save on bandwidth and also on Reducer processing time.</p>
  
  <p>Can this be done in the Combiner phase?  Is this sort of optimization prior to the shuffle phase commonly done?</p>