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: S. Muthu Muthukrishnan. Data Streams: Algorithms and Applications. Überblicksartikel auf S. Muthu Muthukrishnan's Homepage, 39 Seiten. Workshop zu Datenstrom-Algorithmen in Århus, August 2007. Workshop zu Datenstrom-Algorithmen in Kanpur, Dezember 2006. Zu Kommunikationskomplexität: Eyal Kushilevitz. Communication Complexity. Überblicksartikel auf E. Kushilevitz' Homepage, 30 Seiten. Eyal Kushilevitz und Noam Nisan. Communication Complexity. Cambridge University Press, 1999. 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)