Seminar: Algorithmen für große Datenmengen (SS 01)

The course will switch to English if there are students not fluent in German.

Ort:

Nach Vereinbarung, Vorbesprechung Mittwoch 4.4.01, MPII Raum 308, (Geb. 46). (Abweichend vom Vorlesungsverzeichnis)

Dozent:

Ulrich Meyer, Geb. 46, Raum 325, Tel. 0681 9325 125 umeyer@mpi-sb.mpg.de;
PD Dr. Peter Sanders, Geb. 46, Raum 315, Tel. 0681 9325 115, sanders@mpi-sb.mpg.de

Vorkenntnisse:

Info V o.ä.

Scheinvergabe:

Für erfolgreiche Mitarbeit einschließlich eines eigenen Vortrags

Viele Anwendungen z.B. Geographische Informationssysteme, Data Warehouses, Virtuelle Realität, Video-on-Demand, wissenschaftliches Rechnen, elektronische Bibliotheken, WWW-Suchmaschinen haben die Tendenz jede Speicherkapazität aufzufüllen, die bezahlbar ist. Solche Datenmengen werden aus Kostengründen weitgehend auf Festplatten gehalten.

In dieserm Seminar wollen wir Grundlagen von Algorithmen erarbeiten, die solche Datenmengen bewältigen können. Vorläufige Themenübersicht:

Übersicht und Modellierung (Vortrag Peter Sanders)

[1, 2].

Sortieren:

[1, 3] -- ein universeller Baustein für externe Algorithmen. Hier ein Beweis von Kurt Mehlhorn und Andreas Crauser für die unterer Schranke. Ausarbeitung von htmladdnormallink

Prioritätslisten

eine Verallgemeinerung von Sortieren [4, 5, 6, 7].

Suchbäume:

B-Trees und Buffer-Trees [6, 8, 1].

Datenbanken:

Anwendung grundlegender externer Algorithmen in Datenbanken. Ausarbeitung von Thorsten Siffrin.

Strings:

Suffix-Array -- eine einfache Datenstruktur für Volltextsuche [2, 9]. Ausarbeitung von Christian Diehl.

Emulation paralleler Algorithmen

Recycling paralleler Algorithmen [10, 11], Anwendungen: Graphenalgorithmen [12]

Graphenalgorithmen (Vortrag Uli Meyer)

Connected Components, Minimum Spanning Trees, Shortest Paths

Geometrie:

Geometrische Suchbäume. Ausarbeitung von Eric Schwarzkopf.

Je nach Teilnehmerzeit werden wir eine Teilmenge dieser Themen auswählen oder zusätzliche Themen hinzunehmen. Sonderwünsche können u.U. erfüllt werden (Hintergrund für Diplomarbeit XY, mehr Parallelverarbeitung,...)

Literatur

1

J. S. Vitter. External Memory Algorithms. In 6th European Symposium on Algorithms, number 1461 in LNCS, pages 1-25. Springer, 1998.

2

Andreas Crauser. LEDA-SM External Memory Algorithms and Data Structures in Theory and Practice. PhD thesis, Universität des Saarlandes and MPII, 2001.

3

A. Aggarwal and J. S. Vitter. The input/output complexity of sorting and related problems. Communications of the ACM, 31(9):1116-1127, 1988.

4

K. Brengel, A. Crauser, U. Meyer, and P. Ferragina. An Experimental Study of Priority Queues in External Memory. ACM Journal of Experimental Algorithmics, 2001. to appear.

5

Peter Sanders. Fast Priority Queues for Cached Memory. ACM Journal of Experimental Algorithmics, 5, 2000.

6

L. Arge. The buffer tree: A new technique for optimal I/O-algorithms. In 4th WADS, number 955 in LNCS, pages 334-345. Springer, 1995. long version.

7

R. Fadel, K. V. Jakobsen, J. Katajainen, and J. Teuhola. External heaps combined with effective buffering. In 4th Australasian Theory Symposium, volume 19-2 of Australian Computer Science Communications, pages 72-78. Springer, 1997.

8

T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. McGraw-Hill, 1990.

9

A. Crauser and P. Ferragina. A Theoretical and Experimental Study on the Construction of Suffix Array in External Memory. ACM Journal of Experimental Algorithmics, 2001. to appear.

10

F. Dehne, W. Dittrich, and D. Hutchinson. Efficient External Memory Algorithms by Simulating Coarse-Grained Parallel Algorithms. In ACM Symposium on Parallel Architectures and Algorithms, pages 106-115, Newport, RI, 1997.

11

J. Sibeyn and M. Kaufmann. BSP-like external-memory computation. In 3rd Italian Conference on Algorithms and Complexity, pages 229-240, 1997. full version.

12

Y.-J. Chiang, M. T. Goodrich, E. F. Grove, R. Tamasia, D. E. Vengroff, and J. S. Vitter. External memory graph algorithms. In 6th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 139-149, 1995.