  In this paper we study the extraction of representative elements in the data
stream model in the form of submodular maximization. Different from the
previous work on streaming submodular maximization, we are interested only in
the recent data, and study the maximization problem over sliding windows. We
provide a general reduction from the sliding window model to the standard
streaming model, and thus our approach works for general constraints as long as
there is a corresponding streaming algorithm in the standard streaming model.
As a consequence, we obtain the first algorithms in the sliding window model
for maximizing a monotone/non-monotone submodular function under cardinality
and matroid constraints. We also propose several heuristics and show their
efficiency in real-world datasets.
