[Dmbu-l] Data Seminar

Harshal Chaudhari harshal at bu.edu
Thu Nov 10 14:07:47 EST 2016


*Data Seminar*
*Submodular Maximization over Sliding Windows.*
*Alessandro Epasto, Google*
*Friday, November 11, 2016 at 10:30am in Hariri Seminar Room*

*Speaker:* Alessandro Epasto, Google

*Title:* Submodular Maximization over Sliding Windows.

*Abstract:* Maximizing submodular functions under cardinality constraints
lies at the core of numerous data mining and machine learning applications,
including data diversification and summarization. We study this question in
the sliding window model of data streams, where elements arrive one at a
time, and we want to design low-memory and fast update-time algorithms that
maintain a good solution considering only the last W items arrived.

In this context, we provide the first non-trivial algorithm that maintains
a provable approximation of the optimum using space sublinear in the size
of the window. In particular we give a  1/3 -ϵ approximation algorithm that
uses space polylogarithmic in the spread of the values of the elements, and
linear in the solution size k for any constant ϵ > 0 while requiring
polylogarithmic update time. We also show a different algorithm that, at
the cost of using more memory, provides a 1/2 - ϵ approximation thus
matching the best known approximation guarantees for submodular
optimization in insertion-only streams, a less general formulation of the
problem.

We demonstrate the efficacy of the algorithms on a number of real world
datasets, showing that we can preserve high quality solutions in streams
with millions of items, while storing a negligible fraction of them.

Joint work with Silvio Lattanzi, Sergei Vassilvitskii, Morteza
Zadimoghaddam.
Link: https://arxiv.org/abs/1610.09984

*Bio: *Alessandro Epasto is a research scientist at Google NYC in the graph
mining team lead by Vahab Mirrokni. Before joining Google in 2016 he was a
postdoc at Brown University advised by Prof. Eli Upfal. He received a Ph.D.
in Computer Science from Sapienza University of Rome in 2015 where he was
advised by Prof. Alessandro Panconesi and supported by the Google European
Doctoral Fellowship. During his Ph.D. he was three times an intern at
Google. His research interests include problems in large-scale data mining.

--
Harshal Chaudhari
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs-mailman.bu.edu/pipermail/dmbu-l/attachments/20161110/d13b8a11/attachment-0001.html>


More information about the Dmbu-l mailing list