Seminar

Datenstromalgorithmen

Sommersemester 2009

Veranstalter: Christian Sohler
sohlerinformatik.uni-bonn.de
Voraussetzung: Vordiplom/Bachelor
Vorbesprechung: 14.04.2009 ab 8 Uhr
Termin: Dienstags von 8-10 Uhr
Beginn: 14.04.2009
Raum: 304, OH 14
Anmeldung: Christiane Lammersen
clinformatik.uni-bonn.de

Inhalt:

In den letzten Jahren sind immer mehr Anwendungen entstanden, in denen große Datenmengen auftreten. So fallen beispielsweise bei der Überwachung von Netzwerkdatenverkehr, der Verarbeitung von Anfragen an Suchmaschinen oder im Bereich der Finanztransaktionen sehr große Datenmengen an, die häufig nicht in den Hauptspeicher eines Rechners passen. Daher können diese Daten mit klassischen Algorithmen in den seltensten Fällen effizient ausgewertet werden. Man benötigt spezielle Algorithmen, die die Eingabe in einem oder in wenigen Durchläufen über den Datensatz verarbeiten und nur eine kleine Zusammenfassung des gesamten Datensatzes abspeichern. Solche Algorithmen werden auch als Datenstromalgorithmen bezeichnet. Im Seminar sollen Datenstromalgorithmen vorgestellt und analysiert werden.

Einführende Literatur:

  • S. Muthukrishnan. Data Streams: Algorithms and Applications. (Überblicksartikel)
  • Skript zur Vorlesung Datenstromalgorithmen von C. Sohler
  • Skript zur Vorlesung Datenstromalgorithmen von M. Sauerhoff
  • Workshop zu Datenstrom-Algorithmen in Arhus, August 2007.
  • Workshop zu Datenstrom-Algorithmen in Kanpur, Dezember 2006.
  • E. Kushilevitz und N. Nisan. Communication Complexity. Cambridge University Press, 1999.
  • R. Motwani und P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.

    • Vortragsthemen:

    Häufigkeitsmomente:
  • N. Alon, Y. Matias und M. Szegedy. The Space Complexity of Approximating the Frequency Moments. JCSS, 58(1):137-147, 1999.
  • S. Ganguly. Counting Distinct Items over Update Streams. Theoretical Computer Science, 378(3):211-222, 2007.

    • Bestimmung von häufigsten Elementen:
  • G. Cormode und S. Muthukrishnan. What’s hot and what’s not: tracking most frequent items dynamically. PODS 2003, S.296-306.
  • G. S. Manku und R. Motwani. Approximate Frequency Counts over Data Streams. VLDB 2002.

    • Quantile:
  • S. Guha und A. McGregor. Approximate Quantiles and the Order of the Stream. PODS 2006.

    • Count-Min-Sketch:
  • G. Cormode und S. Muthukrishnan. An Improved Data Stream Summary: The Count-Min Sketch and its Applications. J. of Algorithms, 55(1):58-75, 2005.

    • Histogramme:
  • V. Braverman und R. Ostrovski. Smooth Histograms for Sliding Windows. FOCS 2007.
  • A. Gilbert, S. Guha, P. Indyk, Y. Kotidis, S. Muthukrishnan und M. Strauss. Fast, Small-Space Algorithms for Approximate Histogram Maintenance. STOC 2002, S. 389-398.

    • Abstandsmaße:
  • G. Cormode, M. Datar, P. Indyk und S. Muthukrishnan. Comparing Data Streams Using Hamming Norms (How to Zero in). IEEE Trans. on Knowledge and Data Engineering, 15(3):529-540, 2003.
  • Z. Bar-Yossef, T. S. Jayram, R. Kumar und D. Sivakumar. An Information Statistics Approach to Data Stream and Communication Complexity. FOCS 2002.
  • J. Feigenbaum, S. Kannan, M. J. Strauss und M. Viswanathan. An Approximate L1-Difference Algorithm for Massive Data Sets. SIAM J. Comp., 32(1):131-151, 2002.

    • Geometrische Probleme:
  • A. Bagchi, A. Chaudhary, D. Eppstein und M. Goodrich. Deterministic Sampling and Range Counting in Geometric Data Streams. SoCG 2004, S. 144-151.
  • S. Suri, C. Toth und Y. Zhou. Range Counting over Multidimensional Data Streams. SoCG 2004, S. 160-169.
  • P. Indyk. Algorithms for Dynamic Geometric Problems over Data Streams. STOC 2004, S. 373-380.

    • Clustering:
  • K. Chen. On k-Median Clustering in High Dimensions. SODA 2006, S. 1177-1185.
  • S. Guha, A. Meyerson, N. Mishra, R. Motwani und L. O’Callaghan. Clustering Data Streams: Theory and Practice. IEEE Transactions on Knowledge and Data Engineering (TKDE). Special issue on Online Analysis and Querying of Continuous Data Streams, 15(3):515-528, 2003.

    • Kernmengen:
  • T. Chan. Faster Core-Set Constructions and Data-Stream Algorithms in Fixed Dimensions. SoCG 2004, S. 246-258.
  • G. Frahling und C. Sohler. Coresets in Dynamic Geometric Data Streams. STOC 2005, S. 209-217.
  • S. Har-Peled und S. Mazumdar. On Coresets for k-Means and k-Median Clustering. STOC 2004, S. 291-300.

    • Graphenprobleme:
  • J. Feigenbaum, S. Kannan, A. McGregor, S. Suri und J. Zhang. On Graph Problems in a Semi-Streaming Model. Automata, Languages and Programming (2004), S. 531-543.
  • C. Demetrscu, I. Finocchi und A. Ribichini. Trading of Space for Passes in Graph Streaming Problems. PODS 2006.
  • L. S. Buriol, G. Frahling, S. Leonardi, A. Marchetti-Spaccamela und C. Sohler. Counting Triangles in Data Streams. PODS 2006, S. 253-262.

    • Google's Map-Reduce-Modell:
  • J. Feldman, S. Muthukrishnan, A. Sidiropoulos, C. Stein und Z. Svitkina. On the Complexity of Processing Massive, Unordered, Distributed Data. arXiv:cs/0611108v2

    • Untere Schranken:
  • N. Alon, Y. Matias und M. Szegedy. The Space Complexity of Approximating the Frequency Moments. JCSS, 58(1):137-147, 1999.
  • Z. Bar-Yossef, R. Kumar und D. Sivakumar. Sampling Algorithms: Lower Bounds and Applications. STOC 2001, S. 266-275.
  • Z. Bar-Yossef, T. S. Jayram, R. Kumar und D. Sivakumar. Information Theory Methods in Communication Complexity. Conf. on Computational Complexity 2002, S. 93-102.
  • M. Saks und X. Sun. Space Lower Bounds for Distance Approximation in the Data Stream Model. STOC 2002, S. 360-369.


    • 11.03.2009 - Christiane Lammersen