  This paper presents a new, parallel implementation of clustering and
demonstrates its utility in greatly speeding up the process of identifying
homologous proteins. Clustering is a technique to reduce the number of
comparison needed to find similar pairs in a set of $n$ elements such as
protein sequences. Precise clustering ensures that each pair of similar
elements appears together in at least one cluster, so that similarities can be
identified by all-to-all comparison in each cluster rather than on the full
set. This paper introduces ClusterMerge, a new algorithm for precise clustering
that uses transitive relationships among the elements to enable parallel and
scalable implementations of this approach. We apply ClusterMerge to the
important problem of finding similar amino acid sequences in a collection of
proteins. ClusterMerge identifies 99.8% of similar pairs found by a full
$O(n^2)$ comparison, with only half as many operations. More importantly,
ClusterMerge is highly amenable to parallel and distributed computation. Our
implementation achieves a speedup of 604$\times$ on 768 cores (1400$\times$
faster than a comparable single-threaded clustering implementation), a strong
scaling efficiency of 90%, and a weak scaling efficiency of nearly 100%.
