UNIVERSITY OF AARHUS DEPARTMENT OF COMPUTER SCIENCE External Memory Algorithms and Data Structures, Fall 2000 

Lecturers · Time and place · Course description · Schedule · Literature · Projects · Evaluation · Prerequisites · Course language · Credits 
The first lecture are Monday September 4, 12.1513.00, and Thursday September 7, 10.1512.00 in Auditorium D4.
Otherwise lectures are Mondays 12.1514.00 and Thursdays 9.1510.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/Ooperations 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.
Date  Topics  Reading 
Sep. 4  Introduction, I/Omodel (slides)  [A97, pp. 16] 
Sep. 7  Btrees  [GT98, pp. 523524, 658664],[BF00] 
Sep. 11  Merge sort, distribution sort  [A97, pp. 78] 
Sep. 14  Btrees  [BF00] 
Sep. 18  Discussion of project 1A, lower bounds for searching and sorting  [KL92, sect. 1, 2, 3.1, 5] 
Sep. 21  Lower bound for permutation, I/Ocomparisontrees  [KL92, sect. 3.2, 4.1] 
Sep. 25  I/O lower bounds from comparison lower bounds, random permutation  [KL92, sect. 4.2], [S98] 
Sep. 28  Selection  [S99] 
Oct. 2  Selection (slides), Cache oblivious algorithms (slides)  [S99],[FLPR99,sect. 12,4,69] 
Oct. 5  Cache oblivious algorithms  [FLPR99,sect. 4] 
Oct. 9  Cache oblivious Btrees (slides)  [BDF00, sect. 12] 
Oct. 12  Cache oblivious Btrees  [BDF00, sect. 3.1,3.5,4,5] 
Oct. 16  Canceled  
Oct. 19  Canceled  
Oct. 23  Feedback on project 1 (slides), Buffer Trees (slides)  [A95] 
Oct. 26  Buffer Trees  [A95] 
Oct. 30  Rtrees (slides)  [AHVV99] 
Nov. 2  External interval trees  [AV96] 
Nov. 6  External interval trees  [AV96] 
Nov. 9  External priority search trees  [ASV99] 
Nov. 13  Range searching, Trapezoidal decomposition, Triangulation, Endpoint domination  [ASV99],[AVV95] 
Nov. 16  Endpoint domination  [AVV95] 
Nov. 20  Connected components, Minimum spanning trees, Bottleneck minimum spanning trees, Maximal matching  [ABW98, sect. 14,6] 
Nov. 23  Discussion of project 3B  
Nov. 27  Connected components, Minimum spanning trees  [MR99, sect. 5], [ABT00, sect. 12] 
Nov. 30  Minimum spanning trees  [ABT00, sect. 2] 
Dec. 4  String Btrees  [FG99, sect. 14.3,4.57] 
Dec. 7  String Btrees  [FG99] 
Dec. 11  String Sorting  [AFGV97, sect. 13,5] 
Dec. 14  Canceled  
Dec. 18  Final discussion 