  We present a sequential Monte Carlo sampler for coalescent based Bayesian
hierarchical clustering. The model is appropriate for multivariate non-\iid
data and our approach offers a substantial reduction in computational cost when
compared to the original sampler. We also propose a quadratic complexity
approximation that in practice shows almost no loss in performance compared to
its counterpart. Our formulation leads to a greedy algorithm that exhibits
performance improvement over other greedy algorithms, particularly in small
data sets. We incorporate the Coalescent into a hierarchical regression model
that allows joint modeling of multiple correlated outcomes. The approach does
not require {\em a priori} knowledge of either the degree or structure of the
correlation and, as a byproduct, generates additional models for a subset of
the composite outcomes. We demonstrate the utility of the approach by
predicting multiple different types of outcomes using medical records data from
a cohort of diabetic patients.
