# 2014 StreamingSubmodularMaximization

- (Badanidiyuru et al., 2014) ⇒ Ashwinkumar Badanidiyuru, Baharan Mirzasoleiman, Amin Karbasi, and Andreas Krause. (2014). “Streaming Submodular Maximization: Massive Data Summarization on the Fly.” In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2014) Journal. ISBN:978-1-4503-2956-9 doi:10.1145/2623330.2623637

**Subject Headings:** Nonparametric Learning in Massive Datasets Algorithm, Nonparametric Regression.

## Notes

## Cited By

- http://scholar.google.com/scholar?q=%222014%22+Streaming+Submodular+Maximization%3A+Massive+Data+Summarization+on+the+Fly
- http://dl.acm.org/citation.cfm?id=2623330.2623637&preflayout=flat#citedby

## Quotes

### Author Keywords

### Abstract

How can one summarize a massive data set “on the fly", i.e., without even having seen it in its entirety? In this paper, we address the problem of extracting representative elements from a large stream of data. I.e., we would like to select a subset of say k data points from the stream that are most representative according to some objective function. Many natural notions of “representativeness " satisfy submodularity, an intuitive notion of diminishing returns. Thus, such problems can be reduced to maximizing a submodular set function subject to a cardinality constraint. Classical approaches to submodular maximization require full access to the data set. We develop the first efficient streaming algorithm with constant factor [math]1/2-ε[/math] approximation guarantee to the optimum solution, requiring only a single pass through the data, and memory independent of data size. In our experiments, we extensively evaluate the effectiveness of our approach on several applications, including training large-scale kernel methods and exemplar-based clustering, on millions of data points. We observe that our streaming method, while achieving practically the same utility value, runs about 100 times faster than previous work.

## References

;

Author | volume | Date Value | title | type | journal | titleUrl | doi | note | year | |
---|---|---|---|---|---|---|---|---|---|---|

2014 StreamingSubmodularMaximization | Ashwinkumar Badanidiyuru Baharan Mirzasoleiman Amin Karbasi Andreas Krause | Streaming Submodular Maximization: Massive Data Summarization on the Fly | 10.1145/2623330.2623637 | 2014 |

Author | Ashwinkumar Badanidiyuru +, Baharan Mirzasoleiman +, Amin Karbasi + and Andreas Krause + |

conference | KDD-2014 + |

doi | 10.1145/2623330.2623637 + |

proceedings | Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining + |

title | Streaming Submodular Maximization: Massive Data Summarization on the Fly + |

year | 2014 + |