Figure 4.6 Map and reduce functions in MapReduce. In general, the map function
produces a list of key-value pairs. All values for a key are collected into one
list in the reduce phase. This list is then processed further. The instantiations of the
two functions and an example are shown for index construction. Because the map
phase processes documents in a distributed fashion, termID–docID pairs need not be
ordered correctly initially as in this example. The example shows terms instead of
termIDs for better readability. We abbreviate Caesar as C and conquered as c’ed.