We study core-set construction algorithms for the task of Diversity
Maximization under fairness/partition constraint. Given a set of points $P$ in
a metric space partitioned into $m$ groups, and given $k_1,\ldots,k_m$, the
goal of this problem is to pick $k_i$ points from each group $i$ such that the
overall diversity of the $k=\sum_i k_i$ picked points is maximized. We consider
two natural diversity measures: sum-of-pairwise distances and
sum-of-nearest-neighbor distances, and show improved core-set construction
algorithms with respect to these measures. More precisely, we show the first
constant factor core-set w.r.t. sum-of-pairwise distances whose size is
independent of the size of the dataset and the aspect ratio. Second, we show
the first core-set w.r.t. the sum-of-nearest-neighbor distances. Finally, we
run several experiments showing the effectiveness of our core-set approach. In
particular, we apply constrained diversity maximization to summarize a set of
timed messages that takes into account the messages' recency. Specifically, the
summary should include more recent messages compared to older ones. This is a
real task in one of the largest communication platforms, affecting the
experience of hundreds of millions daily active users. By utilizing our
core-set method for this task, we achieve a 100x speed-up while losing the
diversity by only a few percent. Moreover, our approach allows us to improve
the space usage of the algorithm in the streaming setting.

我们研究了在公平性 / 分区约束条件下多样性最大化任务中的一种核心集构建算法。给定一个被划分为 m 组的度量空间中的点集 P，以及给定的每组 i 中的 ki 个点，该问题的目标是从每个组中选择 ki 个点，使得选择的 k 个点的整体多样性最大化。我们考虑了两种自然的多样性度量方法：对点对距离求和和对最近邻距离求和，并展示了针对这些度量方法的改进的核心集构建算法。具体而言，我们展示了第一种相对于点对距离求和而言大小与数据集大小和纵横比无关的核心集，同时我们还展示了第一个相对于最近邻距离求和而言的核心集。最后，我们进行了几个实验证明了我们的核心集方法的有效性。特别是，我们将约束的多样性最大化应用于一个考虑到消息的新旧的定时消息集的总结。具体而言，总结应该包含比较近期的消息而不是较早的消息。这是在一个最大的通信平台中的一个真实任务，每天活跃用户的体验都会受到影响。通过利用我们的核心集方法，我们实现了 100 倍的加速，只损失了少数百分比的多样性。此外，我们的方法还可以改进流式设置中算法的空间利用率。