  The set of answers to a query may be very large, potentially overwhelming
users when presented with the entire set. In such cases, presenting only a
small subset of the answers to the user may be preferable. A natural
requirement for this subset is that it should be as diverse as possible to
reflect the variety of the entire population. To achieve this, the diversity of
a subset is measured using a metric that determines how different two solutions
are and a diversity function that extends this metric from pairs to sets. In
the past, several studies have shown that finding a diverse subset from an
explicitly given set is intractable even for simple metrics (like Hamming
distance) and simple diversity functions (like summing all pairwise distances).
This complexity barrier becomes even more challenging when trying to output a
diverse subset from a set that is only implicitly given such as the query
answers of a query and a database. Until now, tractable cases have been found
only for restricted problems and particular diversity functions.
  To overcome these limitations, we focus on the notion of ultrametrics, which
have been widely studied and used in many applications. Starting from any
ultrametric $d$ and a diversity function $\delta$ extending $d$, we provide
sufficient conditions over $\delta$ for having polynomial-time algorithms to
construct diverse answers. To the best of our knowledge, these conditions are
satisfied by all diversity functions considered in the literature. Moreover, we
complement these results with lower bounds that show specific cases when these
conditions are not satisfied and finding diverse subsets becomes intractable.
We conclude by applying these results to the evaluation of conjunctive queries,
demonstrating efficient algorithms for finding a diverse subset of solutions
for acyclic conjunctive queries when the attribute order is used to measure
diversity.
