Seminar on Streaming Algorithms (Summer 2026)

The seminar is open to all students interested in algorithms and theoretical computer science. Some algorithmic background and general mathematical maturity is expected.

Each student has to perform one presentation in English on a topic related to streaming algorithms. Your grade will be based on how well you can communicate your topic to the audience.

The deadline for emailing me your preferred topic is May 8th, 2026. Along with your preferred topic please email me the set of your preferred presentation dates (final possible presentation: Monday July 20th, 2026). I will try to schedule two presentations per seminar day.

The textbook we will mostly use is Small Summaries for Big Data, by Cormode and Yi. The lecture notes Data Stream Algorithms, by Amit Chakrabarti are also very useful.

A 2-page summary of the topic presented should be delivered to me by email until July 20th, 2026.

Topics will be allocated on a FCFS basis. I will be glad to answer questions on your topic, either by email or by appointment at my office (APB 3002) until your presentation day.

I have tried to group topics in three classes of difficulty, based on prerequisites needed and my view of their complexity.

List of Topics

1. A Simple Streaming Algorithm for Minimum Enclosing Balls, by Zarrabi-Zadeh and Chan (CCCG 2006). Class I.
2. Distinct Elements in Streams: An Algorithm for the (Text) Book, by Chakraborty, Vinodchandran and Meel (ESA 2022). Class II (probability needed)
3. Streaming and Dynamic Algorithms for Minimum Enclosing Balls in High Dimensions, by Chan and Pathak (WADS 2011). Section 2 only. Class I.
4. Space-Efficient Online Computation of Quantile Summaries, by Greenwald and Khanna (SIGMOD 2001). Class III.
5. Counting Distinct Elements in a Data Stream, by Bar-Yossef, Jayram, Kumar, Sivakumar and Trevisan (RANDOM 2002), class III (requires hash functions)
6. The Misra-Gries Algorithm (Ch. 3.2 from textbook, Ch. 1 from notes). Class I.
7. The Morris counter (Ch. 2.1 from textbook, Ch. 4.2-4.3 from notes). Class II (probability needed)
8. Bloom Filters for Set Membership (Ch. 2.7 from textbook). Class II (requires hash functions).
9. The Alon-Matias-Szegedy estimator (Ch. 6 from notes). Class II (probability needed)
10. The Munro-Paterson algorithm (Ch. 11 from notes). Class II
11. Estimating the number of distinct elements (Ch. 2 from notes). Class II (probability needed)
12. (Weighted) Random Sampling (Ch. 2.2 and 2.3 from textbook). Class I.
13. An Optimal Algorithm for Triangle Counting in the Stream, by Jayaram and Kallaugher (RANDOM 2021). Class III (requires hash functions)
14. Algorithms for Dynamic Geometric Problems over Data Streams, by Indyk (STOC 2004). Sections 1-3 only. Class II.
15. An Improved Data Stream Summary: The Count-Min Sketch and its Applications, by Cormode and Muthukrishnan (LATIN 2004). Class III (requires hash functions)
16. The Boyer-Moore Majority Vote algorithm (https://apps.dtic.mil/sti/tr/pdf/ADA131702.pdf), Class I.

Each student is assigned one presentation; no collaborations are allowed.

Assigned Topics

Each presentation should not exceed 40 mins. You may use any of projector or blackboard.

Tentative Schedule (location: APB/3027, time: 09:20, 2nd block)

Kontakt

• Dr. Nick Matsakis
  Tel.: +49 (0) 351 463-38237