VVZ API is not affiliated with ETH Zurich. Data might be outdated or incorrect. Please view the official ETHZ Vorlesungsverzeichnis for binding information.
External Memory Algorithms and Data Structures
Last Updated: 2026-02-05 15:07:00
Abstract
In many applications that work on huge data-sets, the performance bottleneck is the data-transfer between the different levels of the memory, namely processor cache, main memory, and harddisk.This phenomenon is modelled by the so-called external memory or I/O model. We study algorithm design and analysis in this model for problems in sorting and searching, computational geometry, and graphs.
Content
Modern computer systems usually have an entire hierarchy of memory levels, like CPU registers, several levels of memory cache, main memory (RAM), and secondary memory (disk). The performance characteristics across the levels ranges from fast but small to huge but slow. Traditionally, the design of algorithms does not take this memory hierarchy into account, but focuses on the CPU usage and assumes that memory is uniformly as fast as the CPU. For decades, the efficient usage of the memory hierarchy was considered independent of the algorithms: people tried to devise good cache replacement strategies, or data structures that would perform well with all programs. Only recently (since around 1989), the idea of optimizing the algorithm to work well with the memory hierarchy has been carefully studied. This development has certainly been fostered by the decreasing cost for acquiring and storing data that made applications using terabytes of data possible. These applications stem from areas as diverse as astronomy, geology, meteorology, and finance, as well as web search engines, VLSI verification, computer graphics, and geographic information systems (GIS). The basic model assumes a situation where the data set to work on is far bigger than the available main memory and needs to be stored on (a sufficiently large) disk. It focuses on the data transfer between memory and disk, the so called I/O, that usually happens in large blocks. Algorithms designed to minimize the number of I/Os are termed "external memory algorithms". This seminar is devoted to classical and recent results in the area of designing and analysing external memory algorithms and data structures. In contrast to last winter semester, the course "External Memory Algorithms and Data Structures" (EMADS) will not be taught in the winter 2006/07. This seminar will provide topics for newcomers to the area, but there will also be topics that are interesting for students that attended previous EMADS courses.
General Information
- Language
- German
- Levels
- DS
- Frequency
- Yearly recurring
Examination
- Type
- graded semester performance
Course Components
| Type | Title | Time & Place | Hours |
|---|---|---|---|
| seminar | External Memory Algorithms and Data Structures |
|
2 h weekly |