Max and min word occurrence with MapReduce

To find the most and least frequent words, first run a word count job to get the number of occurrences of each word. Then find the maximum and minimum of those counts. This is done either with a second MapReduce job, or with a single job whose reducers keep track of the extremes.

Job 1: Word count

map(offset, line):
    for each word w in line:
        emit(w.lower(), 1)

reduce(word, counts):
    emit(word, sum(counts))

A combiner (same as the reducer) can be used to cut network traffic. Output example for text "to be or not to be": (be,2) (not,1) (or,1) (to,2).

Job 2: Find the global max and min

Every word-count pair is sent to one common key so that a single reducer sees all counts.

map(word, count):
    emit("ALL", (word, count))

reduce("ALL", pairs):
    maxW = pair with highest count
    minW = pair with lowest count
    emit("MAX", maxW)
    emit("MIN", minW)

Because all data goes to one reducer, each mapper should send only its local max and min pairs (just two records), using a combiner or in-mapper combining as below, so the single reducer does not become a bottleneck.

// Mapper2 keeps local extremes in memory, emits in cleanup()
private int maxCnt = Integer.MIN_VALUE, minCnt = Integer.MAX_VALUE;
private String maxWord = "", minWord = "";

public void map(Text word, IntWritable cnt, Context c) {
  if (cnt.get() > maxCnt) { maxCnt = cnt.get(); maxWord = word.toString(); }
  if (cnt.get() < minCnt) { minCnt = cnt.get(); minWord = word.toString(); }
}
protected void cleanup(Context c) throws IOException, InterruptedException {
  c.write(new Text("ALL"), new Text(maxWord + "," + maxCnt));
  c.write(new Text("ALL"), new Text(minWord + "," + minCnt));
}

The reducer then compares the few local extremes from all mappers and writes the global maximum and minimum.

Example

Text: "to be or not to be" gives counts be=2, not=1, or=1, to=2. Max count = 2 (words be and to), min count = 1 (words not and or). In case of ties, the reducer can emit all tied words.

Data flow

 Text -> [Job1: map/reduce] -> (word,count)
      -> [Job2: map -> ALL -> reduce] -> MAX, MIN

Alternatively, with a single reducer in Job 1 (setNumReduceTasks(1)), the reducer can track the running max and min and emit them in cleanup(). This is simple but does not scale as well.