Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

External Memory Algorithms and Data Structures WS04/05
Institute for Theoretical Computer Science | Department of Computer Science | ETH Zurich

External Memory Algorithms and Data Structures

(251-0455-00L) WS 04/05

Current Course

The homepage of the course in WS 05/06 can be found here

Time & Place


Instructors

Lecturer: Riko Jacob
CLW D2/ Tel: (01) 632-7403. e-mail: rjacob@inf.ethz.ch
Lecturer: Peter Widmayer
CLW C2/ Tel: (01) 632-7400. e-mail: widmayer@inf.ethz.ch
Assistant: Yoshio Okamoto
IFW B48.2/ Tel: (01) 632-7148. e-mail: okamotoy@inf.ethz.ch

Schedule


Lectures Materials Exercises References

#1 (October 21)
Introduction
I/O model
Sorting
[PDF] [PDF]

#2 (October 28)
Sorting
IO lower bound, IO comparison trees
Permuting
Optimal merging

[PDF]
[PDF]
[PDF]
[PDF]
[PDF] [AV88] [AKL93]

#3 (November 4)
B-trees, (a,b)-trees
Buffer trees

[PDF]
[PDF]
[PDF] [BF00] [Arg03]

#4 (November 11)
Buffer trees (continued)
[PDF] [Arg03]

#5 (November 18)
Bulk operations in (a,b)-trees
(Guest lecture by Eljas Soisalon-Soininen)
[PDF] [PMSS04] [JLM02] [HMRT86]

#6 (November 25)
Spatial data structures
[PDF] [NW99]

#7 (December 2)
Spatial data structures (continued)
[PDF] [NW99]

#8 (December 9)
Basic design techniques
(by Georg Troxler)
[PPT] [Chap. 3, MSS03]

#9 (January 13)
Elementary graph algorithms
(by Yanic Heer)
[PDF] [Chap. 4, MSS03]

#10 (January 24, Mon @IFW C42)
Storage networks
(by Bálint Miklós)
[PPT] [Chap. 12, MSS03]

#11 (January 28, Fri @IFW D42)
Full-text indexes
(by Christian Sommer)
[PDF] [Chap. 7, MSS03]

#12 (February 4, Fri @ IFW E42)
Cache-oblivious algorithms

[PDF]
[AL93] [AV88] [BBFG+03] [BF02] [BF03] [BFJ02] [FLPR99] [HK81] [Pro99] [ST85]


Course Description

Computer systems usually have an entire hierarchy of memory levels, with each level having its own performance characteristics. Typical memory levels are: CPU registers, several levels of memory cache, main memory (RAM), and secondary memory (disk). Traditionally, the design of algorithms does not take this memory hierarchy into account, but assumes a model with a single level of main memory.

In an increasing number of problems, the amount of data to be processed is far too massive to fit into internal memory. Examples include data collections in astronomy, geology, meteorology, and finance, as well as web search engines, VLSI verification, computer graphics, and geographic information systems (GIS). In such applications, the amount of data may be measured in terabytes.

When dealing with data sets of sizes exceeding main memory, communication between the fast internal memory and the slow external memory is often the performance bottleneck, and the analysis of algorithms under the assumption of a single level of memory may be meaningless.

Instead, a more realistic measure of the efficiency of an algorithm is the number of I/O-operations performed between internal memory and disk. Algorithms designed to minimize this number are termed external memory algorithms.

In this course, we will study the design and analysis of efficient external memory algorithms and data structures. Different paradigms for efficiently solving problems in external memory will be presented, and a number of specific algorithms from areas like sorting and searching, computational geometry, and graphs will be covered.

Language

English

Last modified:Mon Mar 21 00:09:13 2005 by Yoshio Okamoto. Valid HTML 4.0! Valid CSS!