uci-cbcl/genomix — pull request #14 by jakebiesinger (2013-10-20 07:24:00+00:00)
Title: Let's think about scaffolding

The important commit is 90266bb, where instead of one vertex handling the scaffold group-by, there are up to 50,000. The hash spread for the readids is poor: uniform spread would have 5k of data going to each node; this commit fails on the dsm data because one node is receiving 132k of scaffold map messages. I know I can improve the hash code but that will only get us so far.

The group-by is a filtering step, removing some searches that are bound to fail (both endpoints must be "unique"). There's no other reason to group (the search _could_ proceed without knowing the destination kmer at all).

It's been suggested that we try a group-by using hyracks. That would certainly be more performant but there's certainly a lot of dev time that would need to be spent on it. A map-reduce job would be very simple to implement. But these would only help with the filtering and not the subsequent BFS.

Any other thoughts?