title: top 10 path reduction map reduce
body: <p>I am working on a project which needs path navigational graph. </p>
  
  <p>Problem Description:
  To give the project context, the sample UI is expected to look similar to: <a href="http://bl.ocks.org/mbostock/4063570" rel="nofollow">http://bl.ocks.org/mbostock/4063570</a>
  .The difference is that it will be for site navigation. My problem is in dealing with data on the backend.</p>
  
  <p>For user path A->B->C->D->E
  The data format I precomputed looks like this:</p>
  
  <pre><code>Origin:Start:End:Level
  A  A  B  L1
  A  B  C  L2
  A  C  D  L3
  A  D  E  L4
  </code></pre>
  
  <p>Now, assume I have millions of records like this with 100's of Origins, I can group them, aggregate the size and sort by size desc and take the top 10. So for each origin, start and Level, I should have 10 records each.
  So for a graph of 4 levels, I will have 10.. 10^2.. 10^3.. 10^4 for a given start node in graph.</p>
  
  <p>The real problem:
  The top 10 after sorting is not able to take away all not-required L3's and L4's. For a given origin the end of L1 should be the start of L2, the end of L2 should be the start of L3 and so on. Due to this reason I am having many records where many L2 starts do not belonging to L1 end and it multiplies as the level increase.
  Illustration:</p>
  
  <pre><code>A  A  B  L1
  A  B  C  L2
  A  F  G  L2   &lt;-- this comes in top 10 after aggregation, but start is not the end of L1 (B in this case)
  </code></pre>
  
  <p>What I tried: After sorting and slicing top 10, I do a self join for millions of records at each level 1 by 1. I have 10 levels. It is computationally really expensive. </p>
  
  <p>What I am looking for:
  Generic and less expensive Map-reduce solution. Better if I can get it in scalding context.</p>