Assignment 9

Due: We 3/12/08 in class

Goal

Gain some experience with map reduce and hadoop.

1. Setup hadoop on your machine
   • This tutorial should help you getting exlipse hand hadoop working.
   • Try to run the test example described in "Create and Run a Test Job".
   • Write me an email should you have any questions
   • I'll have office hours Fri 3/7/08 11:30 to 12:30 in CSE 002
2. Important hints
   • If you delete any file on the DFS it's gone for all the users. There are no permissions on the DFS. So don't delete anything unless you know exactly what you are deleting!
   • This assignment is very similar to a assignment of 490h
   • All map and reduce tasks belonging to the same key are executed on the same mapper or reducer. They might share some global data!
   • Map and reduce tasks belonging to different key values cannot share any data!
3. Pagerank for Wikipedia
   • Aaron introduced the pagerank algorithm in the Map Reduce lecture (see slides).
   • More informations about the pagerank can be found in this paper
   • Formal definition:

     We assume page A has pages T1...Tn which point to it (i.e., are citations).
     The parameter d is a damping factor which can be set between 0 and 1. We
     usually set d to 0.85. There are more details about d in the next section.
     Also C(A) is defined as the number of links going out of page A. The PageRank
     of a page A is given as follows:
     
     PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))

   • Run the pagerank algorithm on the wikipedia dataset in the DFS: /shared/wikipedia (roughly 12 GB of text in 193 files each sized roughly 64MB) for testing use the /shared/wiki_small
   • Each wikipedia article is stored on its own line. A typical dataset look slike this:

     <page> <title>Critical theory</title>  ... (snip) ...  <text xml:space="preserve">
     In the [[humanities]] and [[social sciences]], '''critical theory''' has two quite different meanings
     with different origins and histories, one originating in [[social theory]] and the other in
     [[literary criticism]]  ... (snip)

   • Notice that the title of the article is delimited by an XML title tag, and the text of the article is delimited by an XML text tag. The links in the article to other wikipedia articles are delimited by "[[" and "]]". Also, certain links will look like this: "[[Longer Real Name|Short Name]]". These links appear in the article with "Short Name" but link to an article titled "Longer Real Name".
4. Hints:
   • Program structure: show
     • You should split your program up into three phases (Building the graph, Iterating over the graph, Producing human readable output)
   • Regexps to parse Wikipedia aricles: show
     • Use of regexp in Java:

       Pattern pat = Pattern.compile( ... );
       Matcher mat = pat.matcher( ... );
       while( mat.find() ){
           String ... = mat.group(1);
           String ... = mat.group(2);
           ...
       }
       

       show
     • Regexp to parse the lines:

       <page.*?>.*?<title.*?>(.*?)</title>.*?<text.*?>(.*?)</text>

       group(1) is the title, group(2) the text. show
     • Regexp to parse the links in the text:

       "\\[\\[(.*?)(\\|.*?)?\\]\\]"

       group(1) is the link target
   • Storing the graph: show
     • Store the graph and the pagerank values in the same datastructure, because hadoop won't allow you to specify two data sources. show
     • The pagerank of a node should be the first "edge" in the graph. Since all map and reduce tasks belonging to the same key are executed on the same mapper / reducer you can store this value in the global memory. show
     • You have to pass nodes of the graph and terms of the pagerank formula to the reducer. You should mark the terms of the pagerank with a certain prefix (eg. "###")