Order preserving hierarchical agglomerative clustering
  Partial orders and directed acyclic graphs are commonly recurring data
structures that arise naturally in numerous domains and applications and are
used to represent ordered relations between entities in the domains. Examples
are task dependencies in a project plan, transaction order in distributed
ledgers and execution sequences of tasks in computer programs, just to mention
a few. We study the problem of order preserving hierarchical clustering of this
kind of ordered data. That is, if we have $a < b$ in the original data and
denote their respective clusters by $[a]$ and $[b]$, then we shall have $[a] <
[b]$ in the produced clustering. The clustering is similarity based and uses
standard linkage functions, such as single- and complete linkage, and is an
extension of classical hierarchical clustering.
  To achieve this, we define the output from running classical hierarchical
clustering on strictly ordered data to be partial dendrograms; sub-trees of
classical dendrograms with several connected components. We then construct an
embedding of partial dendrograms over a set into the family of ultrametrics
over the same set. An optimal hierarchical clustering is defined as the partial
dendrogram corresponding to the ultrametric closest to the original
dissimilarity measure, measured in the p-norm. Thus, the method is a
combination of classical hierarchical clustering and ultrametric fitting.
  A reference implementation is employed for experiments on both synthetic
random data and real world data from a database of machine parts. When compared
to existing methods, the experiments show that our method excels both in
cluster quality and order preservation.
