  Given all pairwise weights (distances) among a set of objects, filtered
graphs provide a sparse representation by only keeping an important subset of
weights. Such graphs can be passed to graph clustering algorithms to generate
hierarchical clusters. In particular, the directed bubble hierarchical tree
(DBHT) algorithm on filtered graphs has been shown to produce good hierarchical
clusters for time series data.
  We propose a new parallel algorithm for constructing triangulated maximally
filtered graphs (TMFG), which produces valid inputs for DBHT, and a scalable
parallel algorithm for generating DBHTs that is optimized for TMFG inputs. In
addition to parallelizing the original TMFG construction, which has limited
parallelism, we also design a new algorithm that inserts multiple vertices on
each round to enable more parallelism. We show that the graphs generated by our
new algorithm have similar quality compared to the original TMFGs, while being
much faster to generate. Our new parallel algorithms for TMFGs and DBHTs are
136--2483x faster than state-of-the-art implementations, while achieving up to
41.56x self-relative speedup on 48 cores with hyper-threading, and achieve
better clustering results compared to the standard average-linkage and
complete-linkage hierarchical clustering algorithms. We show that on a stock
data set, our algorithms produce clusters that align well with human experts'
classification.
