Seminar Details
Improved Sliding Window Algorithms for Clustering and Coverage via Bucketing-Based Sketches
- Start Date: March 23, 2022
- Event Start Time: 11:00 AM
- Event End Time: 12:00 PM
- Seminar Series: Theoretical Computer Science Seminar
- Presenter(s): Peilin Zhong - Google
- Event Location: Online Event
- Event Additional Info: <p>Special Note: The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar. </p> <p>See: <a href="https://theory.cs.rutgers.edu/theory_seminar" target="_blank">https://theory.cs.rutgers.edu/theory_seminar</a> </p>
- Presentation Type: Stand Alone Presentation
- 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.