• German

Main Navigation

Buschjaeger/Honysz/2020b: Very Fast Streaming Submodular Function Maximization

Bibtype Article
Bibkey Buschjaeger/Honysz/2020b
Author Buschjäger, Sebastian and Honysz, Philipp-Jan and Morik, Katharina
Title Very Fast Streaming Submodular Function Maximization
Abstract 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 of more than 7000 experiments, 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.
Year 2020
Projekt SFB876-A1
Url https://arxiv.org/abs/2010.10059
Bibtex Here you can get this literature entry as BibTeX format.