PhD Course on Streaming Algorithms (Spring 2011, Q4)

Messages

Objectives

After attending this course, the participants will be familiar with the state of the art of streaming algorithms/complexities and will have an overview of research directions to pursue in this area.

Learning outcomes and competences

After attending this course, participants should be able to design streaming algorithms using the currently known techniques and analyze their space complexities.

Contents

This course studies data stream algorithms, namely, algorithms that solve a problem by making one pass over the data set while using small memory. These algorithms are important in many application areas such as databases and networking, where data arrives at a high speed and there is no time and/or need to store it for offline processing. We will start with the classical work in this area, followed by a potpourri of recent developments.

Students will be introduced to many data streaming techniques and how they can be applied to solve various problems. The course will focus on the design and theoretical analysis of the algorithms.

Participants are expected to have a basic background in randomized algorithm.

The course will be held in an informal lecture style, meaning that the lecturers have an interactive teaching style that involves the students in discussion and that students are strongly encouraged to initiate discussions themselves, in order to clarify questions they may have.

The evaluation will be based on a set of theoretical exercises and/or individual presentations. The list of questions will be handed out in the middle of the course, and answers are to be submitted by email at the end of the course. The grading is a simple PASS or FAIL.

Detailed list of topics is available in the course plan below (subject to adjustments as we go along).

Lecturers

Qin Zhang (MADALGO) and Lap-Kei Lee (MADALGO).

Place and Time

Turing 014. Every Thursday during April 7 - May 26, 13:00-16:00 (except April 21, which is a holiday)

Course plan

Week Date Content Literature Lecturer Notes
1   Introduction: sampling, distinct elements, heavy hitters [LN], [Mcg], [BYJKST04] Qin Zhang Lessons 1-4
2   Introduction: frequency moments, graph algorithms, geometry [LN], [Mcg], [AMS96], [Guh09], [Ind06]
3   Edit distance, Ulam distance [GJKK07], [EJ08], [AndThesis]
4   Ulam distance. (Intro) lower bounds. [AndThesis] Chapter 5, [LN]
5   Graph algorithms: Maximum matching, Spanners [Mcg05], [Bas08] Lap-Kei Lee
6   Maximum matching (cont'), Sliding window: Basic counting, Lower bound (compressibility argument) [Mcg05], [DGIM02]
7   New directions: Annotations, Distributed streaming [CCG09], [SLN09], [YiZ09], [CLLT10]
Optional   Lower bounds for frequent moments [BYJKS02]

Literature

Quarter

4th (Spring 2011)

Credits

5 ETCS points

Prerequisites

Course language

English

Compulsory programme

Homework hand-in / presentation

Evaluation

Based on mandatory hand-in / presentation and attendance, pass/fail