909de96145d97514b143dfde03e6cd2b-Supplemental-Conference.pdf

We note that both average-linkage and weighted average-linkage are reducible[9]. A challenge in implementing the average-linkage HAC algorithm is to efficiently maintain edge weights inthegraph asvertices (clusters) aremerged. A.2 MotivatingParHAC Recall that our approach is based ongeometric layering, where we group the edges based on their weights and process all edges within the same layer in parallel. Anactivevertexisavertexthat has edges inthe layer currently being processed by the algorithm. A natural idea is to compute a spanning forest induced bytheedges within thecurrent layer,andtomergetogether allvertices ineach tree in the forest.