Algorithms that have to process large data sets have to take into account that the cost of memory accesses depends on where the accessed data is stored. Traditional algorithms design is based on the von Neumann model where accesses to memory have uniform cost. Actual machines increasingly deviate from this model. While waiting for a memory access, modern microproccessors can in principle execute 1000 additions of registers. For hard disk accesses this factor can reach six orders of magnitude.

The goal of this seminar is to collect the main algorithmic techniques used to achieve high performance on memory hierarchies. The focus is on methods that are interesting both from a practical and from a theoretical point of view.

List of Possible Topics

I: Models and Basic Techniques

• Technological aspects (hard disks, caches, tapes, physical and economical aspects,...)
• Modeling, foundations and overview (abstract models, sorting, lower bounds, ...)
• Basic data structures (search trees, priority queues, ...)
• Generic algorithmic approaches (scanning, sorting, time forward processing, emulation of parallel algorithms, ...)

II: Algorithms

• Graphs (connectivity problems, graph exploration, exploiting special graph properties like planarity, ...)
• Geometry (geometric data structures, line segment intersection, triangulations, ...)
• Strings (full text indexing, ...)
• Numerics (linear algebra, FFT, ...)

III: Applications

• Examplary applications of the algorithms
• More applications (machine learning and data mining, multimedia, ...)
• Relations to data bases
• Software libraries

IV: Other Hardware Models

• Handling parallel disks
• Prefetching and caching
• Algorithms for hardware-caches
• Cluster machines for parallel-external computation
• Multi-level memory

The seminar is organized by

• Ulrich Meyer, Max-Planck-Institut für Informatik, Saarbrücken, Germany
• Peter Sanders, Max-Planck-Institut für Informatik, Saarbrücken, Germany
• Jop Sibeyn, Umeå University, Sweden

Applications (possibly including a list of preferred topics) and question should be sent by November 15, 2001 to

Peter Sanders, Email: sanders@mpi-sb.mpg.de
Max-Planck-Institut für Informatik
Stuhlsatzenhausweg 85
66123 Saarbrücken
Germany

Phone: ++49 681-9325 115
Fax: ++49 681-9325 199

About This Seminar Series

• Graph Drawing
• Proof Verification and Approximation Algorithms
• Efficient Methods for Geometric Modelling and Scientific Visualization

Sponsors: