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

Lecturers

Gerth Stølting Brodal and Rolf Fagerberg.

Time and place

Tuesdays 9.15-10.00 in Auditorium D4, and Thursdays 12.15-14.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.

[Pensum ]

Schedule

DateTopicsReading
Sep. 4Introduction, I/O-model (slides)[A97]
Sep. 6Upper and Lower Bounds for Sorting (slides) and Permuting (slides) [A97, Sect. 1-3.2],[KL92, Sect. 1-3.2]
Sep. 11IO-Comparison Trees (slides), Project 1 - Identifying Cache Properties (slides) [KL92, Sect. 4.1-4.2]
Sep. 13Cancelled 
Sep. 18Optimal Merging (slides) 
Sep. 20B-Trees (slides), Cache Oblious Model, Cache Oblivious Search Trees (slides)[BF00][BFJ02][BDF00, Sect. 1-2.1]
Sep. 25Cache Oblivious Search Trees[BDF00, Sect. 1-2.1]
Sep. 27Cache Oblivious Algorithms (slides)[FLPR99, Sect. 1-2,4,6-9]
Oct. 2Feedback on project 1 (slides) 
Oct. 4Feedback on project 1; Introduction to project 2 
Oct. 9Cache Oblivious Sorting[FLPR, Sect. 4]
Oct. 11Buffer Trees (slides)[A95, Sect. 1-3]
Oct. 16Cancelled 
Oct. 18Cancelled 
Oct. 23Buffer Trees[A95]
Oct. 25R-trees (slides)[AHVV99]
Oct. 30External interval trees[AV96]
Nov. 1External interval trees[AV96]
Nov. 6External priority search trees[ASV99, Sect. 1,2.2.1,3.1-3.3.2]
Nov. 8Range searching[ASV99, Sect. 4-5]
Nov. 13Weight balanced B-trees[AV96, Sect. 3.1]
Nov. 15Trapezoidal decomposition, Triangulation, Endpoint domination[AVV95, Sect. 1-3,5]
Nov. 20Discussion of project 3 
Nov. 22Connected components, Minimum spanning trees, Maximal matching[ABW98, Sect. 1-4,6]
Nov. 27Feedback on project 1 
Nov. 29Connected components, Minimum spanning trees[MR99, Sect. 5][ABT00, Sect. 1-2]
Dec. 4The String B-tree[FG99, Sect. 1-4.3,4.5-7]
Dec. 6String Sorting[AFGV97]
Dec. 11String Sorting[AFGV97]
Dec. 13Suffix Tree Construction[FFM00]
Dec. 18Suffix Tree Construction[FFM00]
Dec. 20Cache Oblivious Priority Queues[ABDHM02]

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. [KL92] I/O-complexity of comparison and permutation problems. Mikael Knuden and Kirsten Larsen. Master Thesis, DAIMI, November 1992.
  3. [BF00] Amortized Analysis of (a,b)-Trees, Gerth Stølting Brodal and Rolf Fagerberg, Note, 2000.
  4. [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.
  5. [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.
  6. [BFJ02] Cache-Oblivious Search Trees via Trees of Small Height, Gerth Stølting Brodal, Rolf Fagerberg, and Riko Jacob. In Proc. 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 39-48, 2002.
  7. [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.
  8. [AHVV99] Efficient Bulk Operations on Dynamic R-trees, Lars Arge, Klaus Hinrichs, Jan Vahrenhold, and Jeff Vitter. In Proceedings ALENEX '99, 1999.
  9. [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.
  10. [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
  11. [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.
  12. [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.
  13. [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.
  14. [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.
  15. [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.
  16. [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.
  17. [FFM00] On the Sorting-Complexity of Suffix Tree Construction, Martin Farach-Colton, Paolo Ferragina, S. Muthukrishnan. Journal of the ACM, Vol. 47, No. 6, November 2000, pp. 987-1011.
  18. [ABDHM02] Cache-Oblivious Priority Queue and Graph Algorithm Applications, Lars Arge, Michael A. Bender, Erik D. Demaine, Bryan Holland-Minkley and J. Ian Munro. To appear in Proc. 34th Annual ACM Symposium on Theory of Computing, 2002.

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>.