Distributed Submodular Maximization: Identifying Representative Elements in Massive Data
Citations Over TimeTop 1% of 2013 papers
Abstract
Many large-scale machine learning problems (such as clustering, non-parametric learning, kernel machines, etc.) require selecting, out of a massive data set, a manageable, representative subset. Such problems can often be reduced to maximizing a submodular set function subject to cardinality constraints. Classical approaches require centralized access to the full data set; but for truly large-scale problems, rendering the data centrally is often impractical. In this paper, we consider the problem of submodular function maximization in a distributed fashion. We develop a simple, two-stage protocol GreeDI, that is easily implemented using MapReduce style computations. We theoretically analyze our approach, and show, that under certain natural conditions, performance close to the (impractical) centralized approach can be achieved. In our extensive experiments, we demonstrate the effectiveness of our approach on several applications, including sparse Gaussian process inference on tens of millions of examples using Hadoop.
Related Papers
- → An analysis of approximations for maximizing submodular set functions—I(1978)4,378 cited
- → A threshold of ln n for approximating set cover(1998)3,075 cited
- A Class of Submodular Functions for Document Summarization(2011)
- → Streaming submodular maximization(2014)304 cited
- → Lazier Than Lazy Greedy(2015)178 cited