UNIVERSITY OF AARHUS
DEPARTMENT OF COMPUTER SCIENCE
External Memory Algorithms and Data Structures, Fall 2001
|Lecturers · Time and place · Course description · Schedule · Literature · Projects · Evaluation · Prerequisites · Course language · Credits|
Tuesdays 9.15-10.00 in Auditorium D4, and Thursdays 12.15-14.00 in Auditorium D4.
In an increasing number of problems, the amount of data to be processed is far too massive to fit into internal memory. Examples include VLSI verification, computer graphics, geographic information systems (GIS), and geological and meteorological databases, where the amount of data may be measured in terabytes.
In such applications, the 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 covered, and a number of specific algorithms from areas like computational geometry and GIS will be covered.
|Sep. 4||Introduction, I/O-model (slides)||[A97]|
|Sep. 6||Upper and Lower Bounds for Sorting (slides) and Permuting (slides)||[A97, Sect. 1-3.2],[KL92, Sect. 1-3.2]|
|Sep. 11||IO-Comparison Trees (slides), Project 1 - Identifying Cache Properties (slides)||[KL92, Sect. 4.1-4.2]|
|Sep. 18||Optimal Merging (slides)|
|Sep. 20||B-Trees (slides), Cache Oblious Model, Cache Oblivious Search Trees (slides)||[BF00][BFJ02][BDF00, Sect. 1-2.1]|
|Sep. 25||Cache Oblivious Search Trees||[BDF00, Sect. 1-2.1]|
|Sep. 27||Cache Oblivious Algorithms (slides)||[FLPR99, Sect. 1-2,4,6-9]|
|Oct. 2||Feedback on project 1 (slides)|
|Oct. 4||Feedback on project 1; Introduction to project 2|
|Oct. 9||Cache Oblivious Sorting||[FLPR, Sect. 4]|
|Oct. 11||Buffer Trees (slides)||[A95, Sect. 1-3]|
|Oct. 23||Buffer Trees||[A95]|
|Oct. 25||R-trees (slides)||[AHVV99]|
|Oct. 30||External interval trees||[AV96]|
|Nov. 1||External interval trees||[AV96]|
|Nov. 6||External priority search trees||[ASV99, Sect. 1,2.2.1,3.1-3.3.2]|
|Nov. 8||Range searching||[ASV99, Sect. 4-5]|
|Nov. 13||Weight balanced B-trees||[AV96, Sect. 3.1]|
|Nov. 15||Trapezoidal decomposition, Triangulation, Endpoint domination||[AVV95, Sect. 1-3,5]|
|Nov. 20||Discussion of project 3|
|Nov. 22||Connected components, Minimum spanning trees, Maximal matching||[ABW98, Sect. 1-4,6]|
|Nov. 27||Feedback on project 1|
|Nov. 29||Connected components, Minimum spanning trees||[MR99, Sect. 5][ABT00, Sect. 1-2]|
|Dec. 4||The String B-tree||[FG99, Sect. 1-4.3,4.5-7]|
|Dec. 6||String Sorting||[AFGV97]|
|Dec. 11||String Sorting||[AFGV97]|
|Dec. 13||Suffix Tree Construction||[FFM00]|
|Dec. 18||Suffix Tree Construction||[FFM00]|
|Dec. 20||Cache Oblivious Priority Queues||[ABDHM02]|