Seminar on Algorithms for Database Systems

Main content

Organization:  Peter Widmayer (ETH), Michael Böhlen (UZH)Przemysław Uznański (ETH)

EMails: boehlen AT, przemyslaw.uznanski AT, widmayer AT

Overview and Objectives:
The theme of the seminar this year is Streaming. The seminar will address various topics in this area: Graph Spanners, Graph Sparsification, Sketching, Approximate Counting.

Students learn how to critically read and study research papers, how to summarize the contents of a paper, and how to present it in a seminar.

Teaching Format:
Each participant writes a self-contained report (talk manuscript) of about 10 pages (single-column is fine) and gives a 30 minute presentation. This year again, all presentations will be at the blackboard only. (No computers; no powerpoint!)

Each participant is associated to another participant who serves as a shepherd (aka buddy) for report and presentation. Buddies read the report, make suggestions for improvements, and help with the presentation (e.g., dry runs).

The first version of the report is due three weeks before the date of the presentation. (No excuses!) This first version of the report and presentation will be discussed with the buddy and an advisor one week before the presentation. The final version of the report is due at the talk (new!).

Grading will depend on the quality of the report, talk, active participation during the seminar, and impact as a shepherd.

Setup and Organization:
The setup of the seminar will be discussed on Tuesday, February 23, from 14:15 - 16:00 h in room CAB H 52. In this meeting, the seminar topics will be presented very briefly. They will later be assigned to participants. The seminar talks will be given over a single Saturday: May 7. Participation is mandatory.

Selection of Students/ Papers:
Please select exactly three papers from the list below that you would like to present and list them in descending order of your preferences.
Send the list by email to <przemyslaw.uznanski AT> and with title "Algorithms for Database Systems Seminar - 3 Topics" before Friday (Feb 26) 23:59 midnight. No late emails will be considered. We shall decide the students for this seminar based on your emails. Due to a large number of registrations, unfortunately we cannot ensure that every student who registered may eventually take this seminar, neither we can ensure that a student will be assigned a paper based on his/her top-3 choices of paper list.

Saturday, May 7, the second session of our seminar takes place.

Location: BIN 2.A.01 (ifi, Binzmühlestrasse 14, Oerlikon)
Starting Time: 9:15

The building is locked and we meet at 9:05am at the front entrance (roughly in the middle between tram stops Bahnhof Oerlikon Ost and Leutschenbach)

Final Report:
The final version of the report is due at the talk (new!). The final report must be self-contained, about 10 pages (single-column is fine). Please email your final report to all three organizsers:
boehlen AT, przemyslaw.uznanski AT, widmayer AT


1. Approximate Frequency Counts over Data Streams: Markus Göckeritz
Gurmeet Singh Manku, Rajeev Motwani; Approximate Frequency Counts over Data Streams; Proceedings of the 28th VLDB Conference, 2002.  

buddy: Dominik Stammbach
advisor: Przemysław Uznański  


2. Distributed Stream Join Processing: Thomas Preu 

Qian Lin, Beng Chin Ooi, Zhengkui Wang, Cui Yu; Scalable Distributed Stream Join Processing; SIGMOD’15.  

buddy: Demjan Grubic
advisor: Michael Böhlen  


3. Spark Streaming: Dominik Stammbach
Matei Zaharia, Tathagata Das, Haoyuan Li, Timothy Hunter, Scott Shenker, Ion Stoica; Discretized Streams: Fault-Tolerant Streaming Computation at Scale; SOSP’13.

buddy: Bernard Schroffenegger
advisor: Michael Böhlen


4. spanner construction: Bernard Schroffenegger
— M. Elkin. Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners. ACM Transactions on Algorithms, 7(2):20, 2011.
— M. Elkin and J. Zhang. Efficient algorithms for constructing (1 + epsilon)-spanners in the distributed and streaming models. Distributed Computing, 18(5):375–385, 2006.

buddy: Thomas Preu 
advisor: Przemysław Uznański


5. graph sparsification: Demjan Grubic
— K. J. Ahn and S. Guha. Graph sparsification in the semi-streaming model. In International Colloquium on Automata, Languages and Programming, pages 328–338, 2009.

buddy: Kolitsas Nikolaos
advisor: Przemysław Uznański


6. counting triangles:  Kolitsas Nikolaos
— L. S. Buriol, G. Frahling, S. Leonardi, A. Marchetti-Spaccamela, and C. Sohler. Counting triangles in data streams. In ACM Symposium on Principles of Database Systems, pages 253–262, 2006.  

buddy: Markus Göckeritz
advisor: Peter Widmayer

Page URL:
Sat Jul 22 03:17:31 CEST 2017
© 2017 Eidgenössische Technische Hochschule Zürich