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: 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.

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)