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

Seminar Datenstrom-Algorithmen
Sommersemester 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 Blockseminar fand von Montag, 31.03.2008 bis Mittwoch, 02.04.2008 in Raum 117 (Robert-Mayer-Straße 11-15) statt.
    Das Programm finden Sie hier.
  • Einen sehr schönen Überblick über Grundlagen aus der Stochastik bietet Abschnitt 1.4 des Skriptes zur Vorlesung Internet Algorithmen (Sommersemester 2005) von Prof. Dr. G. Schnitger. (Das Skript können Sie auf der Webseite zur Vorlesung herunterladen.) Abschnitt 4.2 des Skriptes enthält auch eine schöne Darstellung des Reservoir Sampling Algorithmus, mit dem man Stichproben aus Datenströmen gleichverteilt ziehen kann.

    Hash-Tabellen und Hash-Funktionen werden in Abschnitt 8.4 des Buches Randomized Algorithms von Rejeev Motwani und Prabhakar Raghavan (Cambridge University Press, 1995) gut erklärt.

  • Die detaillierten Vortragskonzepte wurden in der Woche vom 25. bis 29. Februar 2008 vorgestellt.
  • Die Vorbesprechung für das Seminar war am 7.2.08 um 14 Uhr in Raum 117 (Robert-Mayer-Straße 11-15)

Programm:

Das Seminar findet in Raum 117 in der Robert-Mayer-Str. 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, 31. März 2008

  • 10:00 - 11:30:  Sairah Ahmed, Auswählen und Sortieren in einem einfachen Datenstrommodell
  • 11:30 - 13:00:  Dirk Müller, Approximation der Häufigkeitsmomente
  • 13:00 - 14:30:  – Mittagspause –
  • 14:30 - 16:00:  Gunnar Rieger, Untere Schranken für den Speicherplatzbedarf zur Approximation der Häufigkeitsmomente
  • 16:00 - 17:30:  Sanaa Falkou, Die Count-Min-Datenstruktur

Dienstag, 1. April 2008

  • 10:00 - 11:30:  Nevin Polat, Eine zufallsbasierte k-Mengen-Datenstruktur
  • 11:30 - 14:30:  – Pause –
  • 14:30 - 16:00:  Alexander Komissarenko, Eine deterministische k-Mengen-Datenstruktur

Mittwoch, 2. April 2008

  • 10:00 - 11:30:  Predrag Jovanic, Berechnung der am häufigsten in einem Datenstrom auftretenden Elemente
  • 11:30 - 13:00:  Prisca Monye, Clustern von Punkten in dynamischen geometrischen Datenströmen
  • 13:00 - 14:30:  – Mittagspause –
  • 14:30 - 16:00:  Sanjiv Kumar, Das StrSort-Modell
  • 16:00 - 17:30:  Walid Bhiri, Graphzusammenhang und Berechnen kürzester Wege im WStream-Modell

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 31. März 2008 bis Mittwoch, den 2. April 2008 statt.

Die Vorbesprechung findet am Donnerstag, den 7. Februar 2008 um 14:15 Uhr in Raum 117 (Robert-Mayer-Straße 11-15) statt.

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 Mitte Februar erarbeiten Sie ein detailliertes Vortragskonzept, das Sie in der Woche vom 25. Februar bis 29. Februar 2008 bei Nicole Schweikardt oder André Hernich vorlegen.

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

Die schriftliche Ausarbeitung Ihres Vortragsthemas (ca. 5 Seiten) geben Sie spätestens am Montag, den 17. März 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.

Interessant könnten auch Teile des Skriptes zur Vorlesung Internet Algorithmen (Sommersemester 2005) von Prof. Dr. G. Schnitger sein. (Das Skript können Sie auf der Webseite zur Vorlesung herunterladen.) Insbesondere bietet es in Abschnitt 1.4 einen Überblick über Grundlagen aus der Stochastik und in Abschnitt 4.2 eine Darstellung des Reservoir Sampling Algorithmus, mit dem man Stichproben aus Datenströmen gleichverteilt ziehen kann.

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.
Sairah Ahmed 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.
Linda Luy 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.
Gunnar Rieger 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.
Markus Knies 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.
Sanaa Falkou 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.
Nevin Polat 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.
Alexander Komissarenko 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.
Konstantin Mörschel 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.
Prisca Monye 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.
Lyse Gatcheussi 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.
Ümit Akdemir 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.
Sanjiv Kumar 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.
Walid Bhiri 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.
Adam Hermann 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.
Tobias Weis 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)

Predrag Jovanic André Hernich

Terminplan:
Do, 07.02.2008: Vorbesprechung (14:15-16:00, Raum 117, Robert-Mayer-Straße 11-15)
Mo, 25.02.2008 bis Fr, 29.02.2008: Vorlage eines detaillierten Vortragskonzepts
Mo, 17.03.2008: Abgabe der schriftlichen Ausarbeitung per E-Mail
Mo, 31.03.2008 bis Mi, 02.04.2008: Blockseminar (Raum 117, Robert-Mayer-Str. 11-15)

Last modified: Fri Apr 04 09:53:40 CEST 2008
André Hernich