Streaming submodular maximization: massive data summarization on the fly

By Ashwinkumar Badanidiyuru, Baharan Mirzasoleiman, Amin Karbasi, Andreas Krause. 2014

387 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Algorithms & Complexity

Citations in the corpus

FastText.zip: Compressing text classification models (2016, methodology): “We refer the reader to two recent surveys by Wang et al. (2014) and Wang et al. (2015) for an overview of the binary hashing literature.”
ConvNets and ImageNet Beyond Accuracy: Explanations, Bias Detection, Adversarial Examples and Model Criticism (2017, methodology): “MMD-critic uses the maximum mean discrepancy [18] and large-scale submodular optimization [3].”
Streaming Weak Submodularity: Interpreting Neural Networks on the Fly (2017, methodology): “02 64 7v 1 [ st Thus, a natural question is whether recent results on streaming algorithms for maximizing submodular functions [Badanidiyuru et al., 2014; Buchbinder et al., 2015; Chekuri et al., 2015] extend to the weakly submodular setting.”
A Practical Online Framework for Extracting Running Video Summaries under a Fixed Memory Budget (2021, methodology): “Furthermore, even though the ‘SieveStreaming’ procedure [1] uses much more memory than our procedure, it uses a submodular objective and has a mathematical performance guarantee.”
Submodular Maximization in Clean Linear Time (2020, neutral): “[5], who obtained (1/2− ε)-approximation for SMC.”
Deletion-Robust Submodular Maximization: Data Summarization with "the Right to be Forgotten" (2017, methodology): “Now, let us consider the case where e is accepted by the i-th instance, SIEVE-STREAMING(i), in the chain.”
Examples are not enough, learn to criticize! Criticism for Interpretability (2016, background): “For example, the pneumonia risk prediction case study in Caruana et al. (2015) showed that a more interpretable model could reveal important but surprising patterns in the data that complex models overlooked.”
ConvNets and ImageNet Beyond Accuracy: Understanding Mistakes and Uncovering Biases (2017, methodology): “MMD-critic uses the maximum mean discrepancy [38] and large-scale submodular optimization [39].”
Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity (2018, background): “…amount of attention in the distributed and streaming literature because of its role in large-scale data mining (Lattanzi et al., 2011; Mirzasoleiman et al., 2013; Badanidiyuru et al., 2014; Kumar et al., 2015; Mirrokni & Zadimoghaddam, 2015; Barbosa et al., 2015; 2016; Liu & Vondrák, 2019).”
Very Fast Streaming Submodular Function Maximization (2020, methodology): “SieveStreaming has the following properties (Badanidiyuru et al., 2014): • It outputs a set S such that |S| ≤ K and f(S) ≥( 1 2 − ε ) OPT • It does 1 pass over the data and stores at most O ( K·log(K) ε ) elements”
Lazier Than Lazy Greedy (2014, background): “Very recently, Badanidiyuru et al. (2014) provided the ﬁrst one-pass streaming algorithm with a constant factor approximation guarantee for general submodular functions without any assumption about the data stream.”