# Core-sets for Fair and Diverse Data Summarization

arXiv: https://arxiv.org/abs/2310.08122 · HTML: https://mlsanity.com/paper/2310.08122/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 43 references that are in the map.
- First posted on arXiv 12 Oct 2023.

## Builds on (most cited first, 19 of 19)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [MiniLM: Deep Self-Attention Distillation for Task-Agnostic Compression of Pre-Trained Transformers](https://mlsanity.com/paper/2002.10957/) (2020)
- [MPNet: Masked and Permuted Pre-training for Language Understanding](https://mlsanity.com/paper/2004.09297/) (2020)
- [Sentence-T5: Scalable Sentence Encoders from Pre-trained Text-to-Text Models](https://mlsanity.com/paper/2108.08877/) (2021)
- [Augmented SBERT: Data Augmentation Method for Improving Bi-Encoders for Pairwise Sentence Scoring Tasks](https://mlsanity.com/paper/2010.08240/) (2020)
- [Abstractive Summarization of Reddit Posts with Multi-level Memory Networks](https://mlsanity.com/paper/1811.00783/) (2018)
- [Fair and Diverse DPP-based Data Summarization](https://mlsanity.com/paper/1802.04023/) (2018)
- [Randomized Composable Core-sets for Distributed Submodular Maximization](https://mlsanity.com/paper/1506.06715/) (2015)
- [Who did They Respond to? Conversation Structure Modeling using Masked Hierarchical Transformer](https://mlsanity.com/paper/1911.10666/) (2019)
- [Randomized Rounding for the Largest Simplex Problem](https://mlsanity.com/paper/1412.0036/) (2014)
- [Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm](https://mlsanity.com/paper/1907.03197/) (2019)
- [Composable Core-sets for Determinant Maximization Problems via Spectral Spanners](https://mlsanity.com/paper/1807.11648/) (2018)
- [Diverse Data Selection under Fairness Constraints](https://mlsanity.com/paper/2010.09141/) (2020)
- [A General Coreset-Based Approach to Diversity Maximization under Matroid Constraints](https://mlsanity.com/paper/2002.03175/) (2020)
- [Improved Approximation and Scalability for Fair Max-Min Diversification](https://mlsanity.com/paper/2201.06678/) (2022)
- [Improved Diversity Maximization Algorithms for Matching and Pseudoforest](https://mlsanity.com/paper/2307.04329/) (2023)
- [Composable Coresets for Constrained Determinant Maximization and Beyond](https://mlsanity.com/paper/2211.00289/) (2022)

## Built on by (most cited first, 4 of 4)

- [GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility](https://mlsanity.com/paper/2405.18754/) (2024)
- [One Period to Rule Them All: Identifying Critical Learning Periods in Deep Networks](https://mlsanity.com/paper/2506.15954/) (2025)
- [Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures](https://mlsanity.com/paper/2506.00165/) (2025)
- [Parameterized and Streaming Algorithms for Euclidean Fair k-Center Clustering](https://mlsanity.com/paper/2609.06384/) (2026)

## Abstract (arXiv)

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 k1,ldots,km, the goal of this problem is to pick ki points from each group i such that the overall diversity of the k=sumi ki 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.