  Maximum diversity aims at selecting a diverse set of high-quality objects
from a collection, which is a fundamental problem and has a wide range of
applications, e.g., in Web search. Diversity under a uniform or partition
matroid constraint naturally describes useful cardinality or budget
requirements, and admits simple approximation algorithms. When applied to
clustered data, however, popular algorithms such as picking objects iteratively
and performing local search lose their approximation guarantees towards maximum
intra-cluster diversity because they fail to optimize the objective in a global
manner. We propose an algorithm that greedily adds a pair of objects instead of
a singleton, and which attains a constant approximation factor over clustered
data. We further extend the algorithm to the case of monotone and submodular
quality function, and under a partition matroid constraint. We also devise a
technique to make our algorithm scalable, and on the way we obtain a
modification that gives better solutions in practice while maintaining the
approximation guarantee in theory. Our algorithm achieves excellent
performance, compared to strong baselines in a mix of synthetic and real-world
datasets.
