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
External Memory Algorithms and Data Structures, Fall 1999

Lecturers

Gerth Stølting Brodal and Rolf Fagerberg.

Time and place

The first lecture are Monday September 4, 12.15-13.00, and Thursday September 7, 10.15-12.00 in Auditorium D4.

Otherwise lectures are Mondays 12.15-14.00 and Thursdays 9.15-10.00 in Auditorium D4.

Course description

Computer systems usually have a whole hierarchy of memory levels, with each level having its own performance characteristics. Typical memory levels are: CPU registers, memory cache, main memory (RAM), and secondary memory storage such as magnetic disks. Traditionally, the design of algorithms do 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 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.

Schedule

DateTopicsReading
Sep. 4Introduction, I/O-model (slides)[A97, pp. 1-6]
Sep. 7B-trees[GT98, pp. 523-524, 658-664],[BF00]
Sep. 11Merge sort, distribution sort[A97, pp. 7-8]
Sep. 14B-trees[BF00]
Sep. 18Discussion of project 1A, lower bounds for searching and sorting[KL92, sect. 1, 2, 3.1, 5]
Sep. 21Lower bound for permutation, I/O-comparison-trees[KL92, sect. 3.2, 4.1]
Sep. 25I/O lower bounds from comparison lower bounds, random permutation[KL92, sect. 4.2], [S98]
Sep. 28Selection[S99]
Oct. 2Selection (slides), Cache oblivious algorithms (slides)[S99],[FLPR99,sect. 1-2,4,6-9]
Oct. 5Cache oblivious algorithms[FLPR99,sect. 4]
Oct. 9Cache oblivious B-trees (slides)[BDF00, sect. 1-2]
Oct. 12Cache oblivious B-trees[BDF00, sect. 3.1,3.5,4,5]
Oct. 16Canceled 
Oct. 19Canceled 
Oct. 23Feedback on project 1 (slides), Buffer Trees (slides)[A95]
Oct. 26Buffer Trees[A95]
Oct. 30R-trees (slides)[AHVV99]
Nov. 2External interval trees[AV96]
Nov. 6External interval trees[AV96]
Nov. 9External priority search trees[ASV99]
Nov. 13Range searching, Trapezoidal decomposition, Triangulation, Endpoint domination[ASV99],[AVV95]
Nov. 16Endpoint domination[AVV95]
Nov. 20Connected components, Minimum spanning trees, Bottleneck minimum spanning trees, Maximal matching[ABW98, sect. 1-4,6]
Nov. 23Discussion of project 3B 
Nov. 27Connected components, Minimum spanning trees[MR99, sect. 5], [ABT00, sect. 1-2]
Nov. 30Minimum spanning trees[ABT00, sect. 2]
Dec. 4String B-trees[FG99, sect. 1-4.3,4.5-7]
Dec. 7String B-trees[FG99]
Dec. 11String Sorting[AFGV97, sect. 1-3,5]
Dec. 14Canceled 
Dec. 18Final discussion 

Literature

  1. [A97] External-Memory Algorithms with Applications in Geographic Information Systems, Lars Arge. In Algorithmic Foundations of Geographic Information Systems, M. van Kreveld, J. Nievergelt, T. Roos and P. Widmayer (Eds.), LNCS Tutorial, Lecture Notes in Computer Science Vol. 1340, Springer-Verlag, 1997.
  2. [GT98] Data Structures and Algorithms in JAVA, Michael T. Goodrich and Roberto Tamassia, John Wiley & Sons, Inc, 1998.
  3. [BF00] Amortized Analysis of (a,b)-Trees, Gerth Stølting Brodal and Rolf Fagerberg, Note, 2000.
  4. [KL92] I/O-complexity of comparison and permutation problems. Mikael Knuden and Kirsten Larsen. Master Thesis, DAIMI, November 1992.
  5. [S98] Random Permutations on Distributed, External and Hierarchical Memory, Peter Sanders. Information Processing Letters 56 (1998) 305-309.
  6. [S99] External Selection, Jop F. Sibeyn. Proceedings of the 16th Symposium Theoretical Aspects of Computer Science, Lecture Notes in Computer Science Vol. 1563, Springer-Verlag, 1999, 291-301.
  7. [FLPR99] Cache-Oblivious Algorithms, Matteo Frigo, Charles E. Leiserson, Harald Prokop, and Sridhar Ramachandran. In Proc. 40th Annual Symposium on Foundations of Computer Science, FOCS '99, October 17-18, 1999, New York, NY, USA.
  8. [BDF00] Cache-Oblivious B-Trees, Michael A. Bender, Erik Demain, and Martin Farach-Colton. In Proc. 41th Annual Symposium on Foundations of Computer Science, FOCS '00, November 12-14, 2000, Redondo Beach, California, USA.
  9. [A95] The Buffer Tree: A New Technique for Optimal I/O Algorithms, L. Arge. Full version of the paper appearing in Proceedings of Fourth Workshop on Algorithms and Data Structures (WADS), Lecture Notes in Computer Science Vol. 955, Springer-Verlag, 1995, 334-345.
  10. [AHVV99] Efficient Bulk Operations on Dynamic R-trees, Lars Arge, Klaus Hinrichs, Jan Vahrenhold, and Jeff Vitter. In Proceedings ALENEX '99, 1999.
  11. [AV96] Optimal Dynamic Interval Management in External Memory, Lars Arge and Jeffrey Scott Vitter. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996, 560-569.
  12. [ASV99] On-Two Dimensional Indexability and Optimal Range Search Indexing, Lars Arge, Vasilis Samoladas, and Jeffrey Scott Vitter. In Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1999
  13. [AVV95] External-Memory Algorithms for Processing Line Segments in Geographic Information Systems, Lars Arge, Darren Vengroff and Jeff Vitter. In Proceedings of the Third European Symposium on Algorithms, Lecture Notes in Computer Science Vol. 979, Springer-Verlag, 1995, 295-310.
  14. [ABW98] A Functional Approach to External Graph Algorithms, James Abello, Adam L. Buchsbaum, and Jeffrey R. Westbrook. In Proceedings of the 6th Annual European Symposium on Algorithms, Lecture Notes in Computer Science Vol. 1461, Springer-Verlag, 1998, 332-43.
  15. [MR99] I/O-Complexity of Graph Algorithms, Kameshwar Munagala and Abhiram Ranade. In Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999, 687-694.
  16. [ABT00] On External Memory MST, SSSP and Multi-way Planar Graph Separation, Lars Arge, Gerth Stølting Brodal, and Laura Toma. In Proc. 7th Scandinavian Workshop on Algorithm Theory, volume 1851 of Lecture Notes in Computer Science, pages 433-447. Springer Verlag, Berlin, 2000.
  17. [FG99] The String B-tree: A New Data Structure for String Search in External Memory and its Applications, Paolo Ferragina, and Roberto Grossi. Journal of the ACM, 46(2), 1999, 236-280.
  18. [AFGV97] On Sorting Strings in External Memory, Lars Arge, Paolo Ferragina, Roberto Grossi, and Jeff Vitter. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing, 1997, 540-548.

Additional literature

Projects
Evaluation
Implementation projects.
Prerequisites
dADS and dAlg.
Course language
Danish or English.
Credits
2 points.
Page maintained by Gerth Stølting Brodal <gerth@cs.au.dk>.