Thanks for your comments. The random gender assign...

2012-01-13T11:04:48.535-08:00

Thanks for your comments. The random gender assignment is not my idea and comes form the original random mate algorithm for the PRAM. It's a "symmetry breaking" technique used in parallel programming in other algorithms. The modification you suggest is also suggested at the end of my first writeup. If we switch from two genders to a total order on the nodes, we can get more mergers of components done per iteration. This implies that the trees representing components can have depth larger than 2, which requires a more powerful and costly flattening phase. It's a trade off and the best option may depend on the type of graph. The blog post you pointed me to has no time complexity discussion in it or linked to, so I am not in a position to comment on which one is faster.

Hey Antonio, Very nice write-up(s). I'm cont...

2012-01-11T13:20:42.191-08:00

Hey Antonio,
Very nice write-up(s).

I'm contemplating 2 options for connected-components MR: yours, and Chaser's (http://chasebradford.wordpress.com/2010/10/23/mapreduce-implementation-for-union-find).

I'm trying to understand some tech details, mainly: how come you had to come up with the gender(donator/acceptor) notion, while in the other alg we simply use natural order of the root node IDs?

Comments on Piccolblog: The connected components example, rewritten using ...

Thanks for your comments. The random gender assign...

Hey Antonio, Very nice write-up(s). I'm cont...