# Streaming Non-monotone Submodular Maximization: Personalized Video Summarization on the Fly

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

## Key facts

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

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

- [Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel](https://mlsanity.com/paper/2111.07917/) (2021)
- [Fast Feature Selection with Fairness Constraints](https://mlsanity.com/paper/2202.13718/) (2022)
- [Adaptive Sampling for Fast Constrained Maximization of Submodular Function](https://mlsanity.com/paper/2102.06486/) (2021)
- [The Power of Subsampling in Submodular Maximization](https://mlsanity.com/paper/2104.02772/) (2021)
- [GPU-Accelerated Optimizer-Aware Evaluation of Submodular Exemplar Clustering](https://mlsanity.com/paper/2101.08763/) (2021)
- [Scalable Distributed Algorithms for Size-Constrained Submodular Maximization in the MapReduce and Adaptive Complexity Models](https://mlsanity.com/paper/2206.09563/) (2022)
- [Practical Parallel Algorithms for Non-Monotone Submodular Maximization](https://mlsanity.com/paper/2308.10656/) (2023)
- [Dynamic Non-monotone Submodular Maximization](https://mlsanity.com/paper/2311.03685/) (2023)
- [γ-weakly θ-up-concavity: A Unified Framework for Non-Convex Optimization Beyond DR-Submodular and OSS Functions](https://mlsanity.com/paper/2602.13506/) (2026)
- [CM-EVS: Sparse Panoramic RGB-D-Pose Data for Complete Scene Coverage](https://mlsanity.com/paper/2605.15597/) (2026)
- [RELS-DQN: A Robust and Efficient Local Search Framework for Combinatorial Optimization](https://mlsanity.com/paper/2304.06048/) (2023)
- [Composable Coresets for Determinant Maximization: Greedy is Almost Optimal](https://mlsanity.com/paper/2309.15286/) (2023)
- [A Dynamic Algorithm for Weighted Submodular Cover Problem](https://mlsanity.com/paper/2407.10003/) (2024)
- [Improving Video Question Answering through query-based frame selection](https://mlsanity.com/paper/2601.07459/) (2026)

## Abstract (arXiv)

The need for real time analysis of rapidly producing data streams (e.g., video and image streams) motivated the design of streaming algorithms that can efficiently extract and summarize useful information from massive data "on the fly". Such problems can often be reduced to maximizing a submodular set function subject to various constraints. While efficient streaming methods have been recently developed for monotone submodular maximization, in a wide range of applications, such as video summarization, the underlying utility function is non-monotone, and there are often various constraints imposed on the optimization problem to consider privacy or personalization. We develop the first efficient single pass streaming algorithm, Streaming Local Search, that for any streaming monotone submodular maximization algorithm with approximation guarantee α under a collection of independence systems cal I, provides a constant 1/big(1+2/√α+1/α +2d(1+√α)big) approximation guarantee for maximizing a non-monotone submodular function under the intersection of cal I and d knapsack constraints. Our experiments show that for video summarization, our method runs more than 1700 times faster than previous work, while maintaining practically the same performance.