bigdatagenomics/adam — pull request #390 by kozanitis (2014-09-19 01:32:30+00:00)
Title: Add Region Join based on interval trees

This is an interval tree based join in the spirit of #366. I haven't tested it at scale yet so I don't know as of now which one is more efficient... Just I bring this implementation for your consideration.

I create an interval tree from all regions of rdd1 which I broadcast to all nodes and I query the tree with all entries of rdd2.

Note that the interval tree uses metadata only, not all contents of rdd1. I keep track of the correspondence between the contents of interval tree and rdd1 through a collection of keys that I zipped with rdd1.