How can we summarize a dynamic data stream when elements selected for the summary can be deleted at any time? This is an important challenge in online services, where the users generating the data may decide to exercise their right to restrict the service provider from using (part of) their data due to privacy concerns. Motivated by this challenge, we introduce the dynamic deletion-robust submodular maximization problem. We develop the first resilient streaming algorithm, called Robust-Streaming, with a constant factor approximation guarantee to the optimum solution. We evaluate the effectiveness of our approach on several real-world applications, including summarizing (1) streams of geo-coordinates (2); streams of images; and (3) click-stream log data, consisting of $45$ million feature vectors from a news recommendation task.

@inproceedings{mirzasoleiman17robust,
	Author = {Baharan Mirzasoleiman and Amin Karbasi and  Andreas Krause},
	Booktitle = {Proc. International Conference on Machine Learning (ICML)},
	Month = {June},
	Title = {Deletion-Robust Submodular Maximization: Data Summarization with ''the Right to be Forgotten"},
	Year = {2017}}