# Differences

This shows you the differences between two versions of the page.

 courses:mapreduce-tutorial:step-13 [2012/01/25 22:19]straka courses:mapreduce-tutorial:step-13 [2012/01/28 23:10]majlis Added links to previous and next chapter. Both sides previous revision Previous revision 2012/01/31 15:54 straka 2012/01/31 15:54 straka 2012/01/31 15:52 straka 2012/01/28 23:10 majlis Added links to previous and next chapter.2012/01/26 23:13 straka 2012/01/25 23:00 straka 2012/01/25 22:53 straka 2012/01/25 22:41 straka 2012/01/25 22:19 straka 2012/01/25 22:19 straka 2012/01/25 15:46 straka vytvořeno Next revision Previous revision 2012/01/31 15:54 straka 2012/01/31 15:54 straka 2012/01/31 15:52 straka 2012/01/28 23:10 majlis Added links to previous and next chapter.2012/01/26 23:13 straka 2012/01/25 23:00 straka 2012/01/25 22:53 straka 2012/01/25 22:41 straka 2012/01/25 22:19 straka 2012/01/25 22:19 straka 2012/01/25 15:46 straka vytvořeno Next revision Both sides next revision Line 1: Line 1: ====== MapReduce Tutorial : Exercise - sorting ====== ====== MapReduce Tutorial : Exercise - sorting ====== + + You are given data consisting of (31-bit integer, string data) pairs. These are available in plain text format: + ^ Path ^ Size ^ + | /net/projects/hadoop/examples/inputs/numbers-small | 3MB | + | /net/projects/hadoop/examples/inputs/numbers-medium | 184MB | + | /net/projects/hadoop/examples/inputs/numbers-large | 916MB | + You can assume that the integers are uniformly distributed. + + Your task is to sort these data. Your solution should work for TBs of data. For that reason, you must use multiple reducers. If your job is executed using //r// reducers, the output consists of //r// files, which when concatenated would produce sorted (key, value) pairs. In other words, each of the output files contains sorted (integer, data) pairs and all keys in one file are either smaller or larger than in other file. + + ===== Nonuniform data ===== + + Assuming uniformity of the integer keys is quite a big deal. Try improving your solution to sort keys with any distribution. You can use the exponentially distributed data available here: + + ^ Path ^ Size ^ + | /net/projects/hadoop/examples/inputs/nonuniform-small | 3MB | + | /net/projects/hadoop/examples/inputs/nonuniform-medium | 160MB | + | /net/projects/hadoop/examples/inputs/nonuniform-large | 797MB | + + Assume we want to produce //r// output files. One of the solutions is to perform two Hadoop jobs: + - Go through the data and sample only a small fraction of the keys. As there are not so many of them, they can fit in one reducer. + - Find best //r-1// integer separators using the sampled data. + - Run the second pass, using the separators to guide the partitioning. + + + ---- + + + +
[[step-12|Step 12]]: Additional output from mappers and reducers.[[.|Overview]][[step-14|Step 14]]: N-gram language model.
+ + + + + + +

[ Back to the navigation ] [ Back to the content ]