# Data Summarization at Scale: A Two-Stage Submodular Approach

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Jun 2018.

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

- [Using Partial Monotonicity in Submodular Maximization](https://mlsanity.com/paper/2202.03051/) (2022)
- [Submodular Minimax Optimization: Finding Effective Sets](https://mlsanity.com/paper/2305.16903/) (2023)
- [Minimax Optimization: The Case of Convex-Submodular](https://mlsanity.com/paper/2111.01262/) (2021)
- [Partial Wasserstein Covering](https://mlsanity.com/paper/2106.00886/) (2021)
- [Feature Cross Search via Submodular Optimization](https://mlsanity.com/paper/2107.02139/) (2021)
- [Sparsification of Decomposable Submodular Functions](https://mlsanity.com/paper/2201.07289/) (2022)
- [Practical 0.385-Approximation for Submodular Maximization Subject to a Cardinality Constraint](https://mlsanity.com/paper/2405.13994/) (2024)
- [The Power of Subsampling in Submodular Maximization](https://mlsanity.com/paper/2104.02772/) (2021)
- [Practical Parallel Algorithms for Non-Monotone Submodular Maximization](https://mlsanity.com/paper/2308.10656/) (2023)
- [Data Summarization beyond Monotonicity: Non-monotone Two-Stage Submodular Maximization](https://mlsanity.com/paper/2309.05183/) (2023)
- [Deep Submodular Peripteral Networks](https://mlsanity.com/paper/2403.08199/) (2024)
- [The Power of Second Chance: Personalized Submodular Maximization with Two Candidates](https://mlsanity.com/paper/2409.03545/) (2024)
- [Online Two-Stage Submodular Maximization](https://mlsanity.com/paper/2510.19480/) (2025)
- [Joint Semantic Token Selection and Prompt Optimization for Interpretable Prompt Learning](https://mlsanity.com/paper/2605.04425/) (2026)

## Abstract (arXiv)

The sheer scale of modern datasets has resulted in a dire need for summarization techniques that identify representative elements in a dataset. Fortunately, the vast majority of data summarization tasks satisfy an intuitive diminishing returns condition known as submodularity, which allows us to find nearly-optimal solutions in linear time. We focus on a two-stage submodular framework where the goal is to use some given training functions to reduce the ground set so that optimizing new functions (drawn from the same distribution) over the reduced set provides almost as much value as optimizing them over the entire ground set. In this paper, we develop the first streaming and distributed solutions to this problem. In addition to providing strong theoretical guarantees, we demonstrate both the utility and efficiency of our algorithms on real-world tasks including image summarization and ride-share optimization.