Theorie komplexer Systeme
Prof. Dr. Nicole Schweikardt
Institut für Informatik
Johann Wolfgang Goethe-Universität
Frankfurt am Main

Seminar Datenstrom-Algorithmen
Wintersemester 2007/2008

Aktuelles   Einführung   Zeit & Raum & Organisation   Literatur   Vortragsthemen   Terminplan    Programm  

Aktuelles:
An dieser Stelle finden Sie im Laufe des Seminars aktuelle Mitteilungen. Bitte sehen Sie regelmäßig nach, ob es Neues gibt.
  • Das Programm finden Sie hier.
  • Das Blockseminar fand von Montag, 11.02.2008 bis Mittwoch, 13.02.2008 in Raum 307 (Robert-Mayer-Straße 11-15) statt.
  • Der Termin für die Abgabe der schriftlichen Ausarbeitungen war am Montag, den 28. Januar 2008.
  • Die detaillierten Vortragskonzepte wurden in der Woche vom 7. bis 11. Januar 2008 vorgestellt.
  • Der Vortrag "Sampling und Hash-Funktionen" fand am Donnerstag, den 22. November 2007 von 14:15 bis 16:00 Uhr in Raum NM 125 statt.
  • Der Vortrag "Grundlegende Begriffe und Resultate aus der Wahrscheinlichkeitsrechnung" fand am Donnerstag, den 15. November 2007 von 14:15 bis 16:00 Uhr in Raum NM 125 statt.
  • Der Vortrag "Einführung in die Kommunikationskomplexität" fand am Donnerstag, den 08. November 2007 von 14:15 bis 16:00 Uhr in Raum NM 125 statt.

Programm:

Das Seminar findet in Raum 307 (Robert-Mayer-Straße 11-15) statt.
Für jeden Vortrag sind 90 Minuten eingeplant: 60 Minuten für den Vortrag und zusätzlich 30 Minuten für Zwischenfragen und Diskussion.

Montag, 11. Februar 2008

  • 10:00 - 11:30:  Dirk Müller, Approximation der Häufigkeitsmomente
  • 11:30 - 13:00:  Oguz Tuna, Untere Schranken für den Speicherplatzbedarf zur Approximation der Häufigkeitsmomente
  • 13:00 - 14:30:  – Mittagspause –
  • 14:30 - 16:00:  Ericson Hölzchen, Die Count-Min-Datenstruktur

Dienstag, 12. Februar 2008

  • 10:00 - 11:30:  Stefan Witt, Eine zufallsbasierte k-Mengen-Datenstruktur
  • 11:30 - 13:00:  Kun Qian, Zählen von Dreiecken

Mittwoch, 13. Februar 2008

  • 10:00 - 11:30:  Thomas Neugebauer, Berechnen von Matchings im Semi-Streaming-Modell
  • 11:30 - 13:00:  Thomas Göldner, Das StrSort-Modell
  • 13:00 - 14:30:  – Mittagspause –
  • 14:30 - 16:00:  Zeeshan Khan, Graphzusammenhang und Berechnen kürzester Wege im WStream-Modell
  • 16:00 - 17:30:  Desislava Ilieva, Berechnung der am häufigsten in einem Datenstrom auftretenden Elemente

Einführung:

Ein Datenstrom ist eine Folge von Daten, auf die nur nach und nach zugegriffen werden kann. Datenstrom-Algorithmen müssen mit sehr wenig Speicher auskommen, und können oft nur eine Approximation der Lösung berechnen. In diesem Seminar werden wir Techniken zum Entwurf und zur Analyse von Datenstrom-Algorithmen sowie die Beschränkungen solcher Algorithmen (untere Schranken) genauer untersuchen. Randomisierung ist beim Entwurf essentiell und tritt in Form von Sampling und Hashing auf. Die unteren Schranken werden oft mittels Kommunikationskomplexität bewiesen.

Das Seminar richtet sich an Studierende mit guten Kenntnissen in theoretischer Informatik.

Zeit, Raum und Organisation:

Das Seminar ist als Blockveranstaltung organisiert und findet vom Montag, den 11. Februar 2008 bis Mittwoch, den 13. Februar 2008 statt.

Vorbesprechung und Themenvergabe finden in der zweiten Semesterwoche am Donnerstag, den 25. Oktober 2007 um 14:15 Uhr in Raum NM 125 statt. Zusätzlich wird es zwei einführende Vorträge in die für das Seminar wichtigsten Begriffe und Techniken geben: am Donnerstag, den 8. November 2007 und 15. November 2007, jeweils um 14:15 Uhr in Raum NM 125.

Für jeden Vortrag werden 90 Minuten eingeplant: 60 Minuten für den Vortrag und zusätzlich 30 Minuten für Zwischenfragen und Diskussion.

Bis Anfang Januar erarbeiten Sie ein detailliertes Vortragskonzept, das Sie in der Woche vom 7. Januar bis 11. Januar 2008 bei Nicole Schweikardt oder André Hernich vorlegen.

Vereinbarung: Wer sein Konzept nicht bis spätestens 11. Januar 2008 vorgestellt hat, nimmt nicht an dem Seminar teil.

Die schriftliche Ausarbeitung Ihres Vortragsthemas (ca. 5 Seiten) geben Sie spätestens am Montag, den 28. Januar 2008 per E-Mail ab. Die Ausarbeitungen werden ausgedruckt und im Blockseminar ausgeteilt.

Einführende Literatur:
Zu Datenstrom-Algorithmen: Zu Kommunikationskomplexität: Zum Entwurf und zur Analyse von randomisierten Algorithmen:
  • Rejeev Motwani und Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, 1995.
  • Noga Alon und Joel Spencer. The Probabilistic Method. Wiley-Interscience, 2000.
Die oben genannten Bücher bzw. Überblicksartikel befinden sich auch im Semesterapparat zum Seminar Datenstrom-Algorithmen in der Informatik-Bibliothek.

Vortragsthemen:
Nr. Thema Vortragende(r) Betreuer
1.

Auswählen und Sortieren in einem einfachen Datenstrommodell

J. Ian Munro und Mike S. Paterson. Selection and Sorting with Limited Storage. Theoretical Computer Science 12, S. 315-323, 1980.
Jana Böckling André Hernich
2.

Approximation der Häufigkeitsmomente

Abschnitte 1 und 2 aus:
Noga Alon, Yossi Matias und Mario Szegedy. The Space Complexity of Approximating the Frequency Moments. Journal of Computer and System Sciences 58(1), S. 137-147, 1999.
Dirk Müller Nicole Schweikardt
3.

Untere Schranken für den Speicherplatzbedarf zur Approximation der Häufigkeitsmomente

Abschnitt 3 aus:
Noga Alon, Yossi Matias und Mario Szegedy. The Space Complexity of Approximating the Frequency Moments. Journal of Computer and System Sciences 58(1), S. 137-147, 1999.
Oguz Tuna Nicole Schweikardt
4.

Berechnungen auf Datenströmen mit mehreren Durchläufen

Monika Rauch Henzinger, Prabhakar Raghavan und Sridar Rajagopalan. Computing on Data Streams. Technischer Bericht 1998-011, DEC Systems Research Center, 1998.
Brent Lyday Nicole Schweikardt
5.

Die Count-Min-Datenstruktur

Abschnitte 1-4 (evtl. auch 5) aus:
Graham Cormode und S. Muthu Muthukrishnan. An Improved Data Stream Summary: The Count-Min Sketch and Its Applications. Journal of Algorithms 55(1), S. 58-75, 2005.
Ericson Hölzchen André Hernich
6.

Eine zufallsbasierte k-Mengen-Datenstruktur

Abschnitte 1 und 2 aus:
Sumit Ganguly. Counting Distinct Items over Update Streams. Theoretical Computer Science 378(3), S. 211-222, 2007.
Stefan Witt Nicole Schweikardt
7.

Eine deterministische k-Mengen-Datenstruktur

Abschnitte 1-4 aus:
Sumit Ganguly und Anirban Majumder. Deterministic k-Set Structure. Revision der Arbeit aus PODS 2006, S. 280-289.
Ljuljzim Aljimi Nicole Schweikardt
8.

Clustern von Punkten in statischen geometrischen Datenströmen

Abschnitte 1-3 (außer 3.4) aus:
Sudipto Guha, Adam Meyerson, Nina Mishra, Rajeev Motwani und Liadan O'Callaghan. Clustering Data Streams: Theory and Practice. IEEE Transactions on Knowledge and Data Engineering 15(3), S. 515-528, 2003.
Gökhan Bal André Hernich
9.

Clustern von Punkten in dynamischen geometrischen Datenströmen

Abschnitte 1-4 aus:
Gereon Frahling und Christian Sohler. Coresets in Dynamic Geometric Data Streams. STOC 2005, S. 209-217.
Lei Zhang André Hernich
10.

Zählen von Dreiecken

Abschnitte 1-3 aus:
Luciana S. Buriol, Gereon Frahling, Stefano Leonardi, Alberto Marchetti-Spaccamela und Christian Sohler. Counting Triangles in Data Streams. PODS 2006, S. 253-262.
Kun Qian André Hernich
11.

Berechnen von Matchings im Semi-Streaming-Modell

Abschnitte 1-3 aus:
Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri und Jian Zhang. On Graph Problems in a Semi-Streaming Model. Theoretical Computer Science 348(2-3), S. 207-216, 2005.
Thomas Neugebauer André Hernich
12.

Das StrSort-Modell

Abschnitte 1-4 aus:
Gagan Aggarwal, Mayur Datar, Sridhar Rajagopalan und Matthias Ruhl. On the Streaming Model Augmented with a Sorting Primitive. FOCS 2004, S. 540-549.
Thomas Göldner André Hernich
13.

Graphzusammenhang und Berechnen kürzester Wege im WStream-Modell

Abschnitte 1-2 aus:
Camil Demetrescu, Irene Finocchi und Andrea Ribichini. Trading Off Space for Passes in Graph Streaming Problems. SODA 2006, S. 714-723.
Zeeshan Khan Nicole Schweikardt
14.

Datenströme mit zufälliger Anordnung der Elemente

Sudipto Guha und Andrew McGregor. Approximate Quantiles and the Order of the Stream. PODS 2006, S. 253-262.
André Hernich
15.

Speicherplatzbedarf zur Anfrageauswertung in XML-Datenströmen

Ziv Bar-Yossef, Marcus Fontoura und Vanja Josifovski. Buffering in Query Evaluation over XML Streams. PODS 2005, S. 216-227.
Andreas Fürtig Nicole Schweikardt
16.

Berechnung der am häufigsten in einem Datenstrom auftretenden Elemente

Abschnitte 1-4 aus:
Graham Cormode und S. Muthu Muthukrishnan. What's Hot and What's Not: Tracking Most Frequent Items Dynamically. Transactions on Database Systems 30(1), S. 249-278, 2005.

Siehe auch Abschnitt 1-3 in der Konferenzversion (PODS 2003)

Desislava Ilieva André Hernich

Terminplan:
Do, 25.10.2007: Vorbesprechung und Themenvergabe (14:15-16:00, Raum NM 125)
Do, 08.11.2007: Vortrag "Einführung in die Kommunikationskomplexität" (14:15-16:00, Raum NM 125)
Do, 15.11.2007: Vortrag "Grundlegende Begriffe und Resultate aus der Wahrscheinlichkeitsrechnung" (14:15-16:00, Raum NM 125)
Do, 22.11.2007: Vortrag "Sampling und Hash-Funktionen" (14:15-16:00, Raum NM 125)
Mo, 07.01.2008 bis Fr, 11.01.2008: Vorlage eines detaillierten Vortragskonzepts
Mo, 28.01.2008: Abgabe der schriftlichen Ausarbeitung per E-Mail
Mo, 11.02.2008 bis Mi, 13.02.2008: Blockseminar (Raum 307, Robert-Mayer-Straße 11-15)

Zuletzt geändert: 2008-03-07
André Hernich