# Common Examples of MapReduce Jobs

## WordCount

WordCount is the most common example of MapReduce.

**Goal**: Count the number of occurrences of each word in a file

**Input to Mappers**: Chunks of the input file

**Mapper Output**: (word, 1) pairs

**Input to Reducers**: (word, <1, 1, 1, ..., 1>) pairs

**Operation at Reducer**: Sum up the values for each word to get the count and output (word, count) pairs

**Output of MapReduce Job**: File containing (word, count) pairs

## Filtering

**Goal**: Filter out records that are of no interest

**Input to Mappers**: Chunks of the input file

**Mapper Output**: Filtered records

**Input to Reducer**: Filtered records grouped by key

**Output of MapReduce Job**: Filtered records

We perform filtering at the mappers itself because the sort/shuffle phase of MapReduce is I/O heavy, and we want to reduce the dataset as much as possible in the map phase itself.

![](https://692505235-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M5-0RGlgjkePcvzcwjB%2F-M5-0TDUmbHuXFo5fa3Q%2F-M5-0TgIx2m-ZfqmjX5z%2FFiltering.png?generation=1586990811417889\&alt=media)

Basically, instead of emitting all (key, value) pairs, the mappers will emit only those pairs that meet a certain condition:

```
Map(k,v) {
if (f(k,v))  // check condition (filter)
{    
// do something
emit()
}
}
```

## Top k

**Goal**: Select the top k records given any number of input records

**Input to Mappers**: Chunks of the input file (several records)

**Mapper Output**: Local top k records (each mapper will output top k records depending on its input records)

**Input to Reducer**: Top k records based on input records from mappers

**Output of MapReduce Job**: Top k records from the entire dataset

![](https://692505235-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M5-0RGlgjkePcvzcwjB%2F-M5-0TDUmbHuXFo5fa3Q%2F-M5-0TgK6Y6C_SqZmNIC%2FTopK.png?generation=1586990812014121\&alt=media)

So, instead of analysing all *n* records at once, the reducer only has to process *k\*m* records (where *m* is the number of mappers)

## Binning

**Goal**: Move records into bins/categories, irrespective of the order of records

*But partitioners do the exact same task! Why use binning?* We use binning because the task of partitioners is I/O intensive.

In binning, the mappers receive chunks of the input file. The mappers itself categorize records into bins. **There is no need for a reducer**. We simply concatenate the intermediate results of the mappers to get the records in each bin.

![](https://692505235-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M5-0RGlgjkePcvzcwjB%2F-M5-0TDUmbHuXFo5fa3Q%2F-M5-0TgMiiH8d_MzrXwr%2FBinning.png?generation=1586990813432423\&alt=media)

## Other Applications

MapReduce can also be used for **Breadth First Search** (BFS) and **PageRank** (Google's algorithm to rank websites in their search engine results). I have not covered their implementations in detail.

**The next section lists the advantages and disadvantages of MapReduce programming.**
