Peilin Zhong, Google

Abstract

Streaming computation plays an important role in large-scale data analysis.

The sliding window model is a model of streaming computation which also captures the recency of the data. In this model, data arrives one item at a time, but only the latest W data items are considered for a particular problem. The goal is to output a good solution at the end of the stream by maintaining a small summary during the stream.

In this work, we propose a new algorithmic framework for designing efficient sliding window algorithms via bucketing-based sketches. Based on this new framework, we develop space-efficient sliding window algorithms for k-cover, k-clustering and diversity maximization problems.
For each of the above problems, our algorithm achieves (1+-varepsilon)-approximation.
Compared with the previous work, it improves both the approximation ratio and the space.

This is a joint work with Alessandro Epasto, Mohammad Mahdian and Vahab Mirrokni.

Special Note: The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar. 

See: https://theory.cs.rutgers.edu/theory_seminar