bigdatagenomics/adam — pull request #366 by fnothaft (2014-08-29 22:30:12+00:00)
Title: [ADAM-366] Add parallel region multi-join.

This adds a region multi-join implementation that executes in parallel, as a possible replacement/accompaniment to #117. CC'ing @tdanford @carlyeks for review.

The parallel join implementation roughly follows the following process:

* We identify all regions that overlap across the two RDDs by projecting the regions down into positions. We keep the position that is the "lowest" point at which the two regions intersect. From this point, we then project the two intersecting regions as a key-value pair.
* From the KV pair RDD, we group-by with the right RDD in the join, which provides us with collections of elements that map to regions from the left RDD.
* We then union that RDD with the left RDD, and group-by the region that all points map to.
* From this RDD, for every region that has points from both the left and the right RDDs, we take a cartesian-ish product of the two sets.

This PR _could_ be merged in it's current state, but I'd like to refactor it a bit more. Specifically, it's sufficiently general to also support region contain multi-joins (e.g., we join all regions from the right RDD with regions from the left RDD that fully contain the region) with a small amount of refactoring. I'll take care of that in the next few days; just wanted to get this PR out there for comment.