title: MapReduce advanced algorithm on Reversed Web-Link Graph (from google paper)
body: <p>I was poking around Hadoop MapReduce after reading the paper from google: <a href="http://static.googleusercontent.com/media/research.google.com/en//archive/mapreduce-osdi04.pdf" rel="nofollow">MapReduce: Simplified Data Processing on Large Clusters</a></p>
  
  <p>I worked on the Reversed Web-Link Graph because it seems interesting, and actually it was quite easy when I code it. So now I have value pairs (target, list&lt;<em>source1, source2, ...</em>>) in the MapReduce output as I had the <a href="http://commoncrawl.org" rel="nofollow">CommonCrawl</a> files as input. (In every value pair, source1/source2/... are the URLs that has a hyperlink links to the target.) I have the output format as "target &lt;<em>tab</em>> source1|source2|..." where each line represents a value pair.</p>
  
  <p>I tried to work on this a little further so I decide to find out if I can have the target source pairs that are 2 links away or more. Then I'm stuck for weeks.</p>
  
  <hr>
  
  <p>I first tried to have my output file as input file to the mapper, and it shall output (target, list&lt;<em>source1, source2, ...</em>>) pairs for reducer to process, where the target is the key. The reducer then track each source, and replace the source by the list value from the corresponding pair where the source is actually the same as the target (the key). Ex: I have (target1, list&lt;<em>source1, source2</em>>),(target2, list&lt;<em>source2, source3</em>>) and (target3, list&lt;<em>source3, source4</em>>) where target2 = source1 and target3 = source2, the output should then be (target1, list&lt;<em>source2, source3, source4</em>>).</p>
  
  <p><strong>Question 1:</strong>
  This doesn't seem to work. I think the reason is that these target1, target2 and target3 keyed value pairs might not be in the same reducer. And MapReduce doesn't have something like a lookup table or I don't know its existance. Am I right? (I read a thing called distributed cache, but here I'm talking about every value pair might be needed, so this would be a huge file which is known undesired when using distributed cache.)</p>
  
  <hr>
  
  <p>So I tried looking for some other algorithm, and <a href="http://www.johnandcailin.com/blog/cailin/breadth-first-graph-search-using-iterative-map-reduce-algorithm" rel="nofollow">breadth first search</a> looks promising. However, I found that BFS always has a starting node, where every value pair in my design is a starting node, so I'm stuck again.</p>
  
  <p><strong>Question 2:</strong>
  Is there any possible modification I can do to make it fit my design?</p>
  
  <hr>
  
  <p>I then realized that most algorithms in MapReduce are playing around with the key  and the customized value field. So I tried to come out with an algorithm that will make my mapper output the same key for the three value pairs I mentioned in the above example.</p>
  
  <p><strong>Question 3:</strong>
  Any idea for this third approach?</p>
  
  <p>Thanks for reading and any possible suggestions.</p>