Here are a few simple examples of interesting programs that can be easily expressed as MapReduce computations.

2.3.0.1 Distributed Grep:
The map function emits a line if it matches a supplied pattern. The reduce function is an identity function that just copies the supplied intermediate data to the output.

2.3.0.2 Count of URL Access Frequency:
The map function processes logs of web page requests and outputs $\left<\mbox{{\tt URL}}, \mbox{{\tt 1}}\right>$. The reduce function adds together all values for the same URL and emits a $\left<\mbox{{\tt URL}}, \mbox{{\tt total count}}\right>$ pair.

2.3.0.3 Reverse Web-Link Graph:
The map function outputs $\left<\mbox{{\tt target}}, \mbox{{\tt source}}\right>$ pairs for each link to a target URL found in a page named source. The reduce function concatenates the list of all source URLs associated with a given target URL and emits the pair: $\left<\mbox{{\tt target}}, \mbox{{\tt$list(\mbox{source})$}}\right>$

2.3.0.4 Term-Vector per Host:
A term vector summarizes the most important words that occur in a document or a set of documents as a list of $\left< word, frequency \right>$ pairs. The map function emits a $\left<\mbox{{\tt hostname}}, \mbox{{\tt term vector}}\right>$ pair for each input document (where the hostname is extracted from the URL of the document). The reduce function is passed all per-document term vectors for a given host. It adds these term vectors together, throwing away infrequent terms, and then emits a final $\left<\mbox{{\tt hostname}}, \mbox{{\tt term vector}}\right>$ pair.

2.3.0.5 Inverted Index:
The map function parses each document, and emits a sequence of $\left<\mbox{{\tt word}}, \mbox{{\tt document ID}}\right>$ pairs. The reduce function accepts all pairs for a given word, sorts the corresponding document IDs and emits a $\left<\mbox{{\tt word}}, \mbox{{\tt$list(\mbox{document ID})$}}\right>$ pair. The set of all output pairs forms a simple inverted index. It is easy to augment this computation to keep track of word positions.

2.3.0.6 Distributed Sort:
The map function extracts the key from each record, and emits a $\left<\mbox{{\tt key}}, \mbox{{\tt record}}\right>$ pair. The reduce function emits all pairs unchanged. This computation depends on the partitioning facilities described in Section 4.1 and the ordering properties described in Section 4.2.