# Very Fast Streaming Submodular Function Maximization

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Oct 2020.

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

- [Data-Efficient Structured Pruning via Submodular Optimization](https://mlsanity.com/paper/2203.04940/) (2022)
- [Active Learning for Deep Neural Networks on Edge Devices](https://mlsanity.com/paper/2106.10836/) (2021)
- [CATRO: Channel Pruning via Class-Aware Trace Ratio Optimization](https://mlsanity.com/paper/2110.10921/) (2021)
- [GPU-Accelerated Optimizer-Aware Evaluation of Submodular Exemplar Clustering](https://mlsanity.com/paper/2101.08763/) (2021)
- [Providing Meaningful Data Summarizations Using Exemplar-based Clustering in Industry 4.0](https://mlsanity.com/paper/2105.12026/) (2021)
- [Key Patch Proposer: Key Patches Contain Rich Information](https://mlsanity.com/paper/2402.11458/) (2024)

## Abstract (arXiv)

Data summarization has become a valuable tool in understanding even terabytes of data. Due to their compelling theoretical properties, submodular functions have been in the focus of summarization algorithms. These algorithms offer worst-case approximations guarantees to the expense of higher computation and memory requirements. However, many practical applications do not fall under this worst-case, but are usually much more well-behaved. In this paper, we propose a new submodular function maximization algorithm called ThreeSieves, which ignores the worst-case, but delivers a good solution in high probability. It selects the most informative items from a data-stream on the fly and maintains a provable performance on a fixed memory budget. In an extensive evaluation, we compare our method against 6 other methods on 8 different datasets with and without concept drift. We show that our algorithm outperforms current state-of-the-art algorithms and, at the same time, uses fewer resources. Last, we highlight a real-world use-case of our algorithm for data summarization in gamma-ray astronomy. We make our code publicly available at https://github.com/sbuschjaeger/SubmodularStreamingMaximization.