UNIVERSITY OF AARHUS
DEPARTMENT OF COMPUTER SCIENCE

External Memory Algorithms and Data Structures, Fall 1999
Lecturers · Time and place · Course description · Schedule · Literature · Projects · Evaluation · Prerequisites · Course language · Credits

Lecturers

Gerth Stølting Brodal and Rolf Fagerberg.

Time and place

Except for the first week lectures take place Tuesdays 9.15-10.00 and Fridays 9.15-11.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. 1Introduction, I/O-model, Merge sort, Distribution sort[A97, pp. 1-8]
Sep. 3 B-trees[GT98, pp. 523-524, 658-664]
Sep. 7B-trees[F99]
Sep. 10Heaps in External Memory[FJKT99]
Sep. 14Discussion of Project 1A 
Sep. 17Buffer Trees[A95]
Sep. 21Batched Range Searching[A95]
Sep. 24 Selection, Permutation lower bound[KL92]
Sep. 28Discussion of Project 1B 
Oct. 1Sorting lower bound[KL92]
Oct. 5Simulation of Parallel Algorithms: Random Permutations[S98]
Oct. 8Random Permutations, Introduction to Orthogonal Range Searching[S98],[ASV99]
Oct. 12Orthogonal Range Searching[ASV99]
Oct. 15Orthogonal Range Searching[ASV99]
Oct. 19Canceled 
Oct. 22Canceled 
Oct. 26Weight balanced B-trees[ASV99]
Oct. 29Stabbing queries[AV96]
Nov. 2Discussion of Project 2, Segment trees 
Nov. 5Trapezoidal decomposition, Triangulation, Endpoint domination[AVV95]
Nov. 9Endpoint domination[AVV95]
Nov. 12R-trees[AHVV99]
Nov. 16SB-trees[FG99]
Nov. 19SB-trees[FG99]
Nov. 23String sorting[AFGV97]
Nov. 26String sorting, Introduction to Project 3[AFGV97]
Nov. 30Connected components[ABW98]
Dec. 3Minimum spanning trees, Maximal matching, Breadth first search, Connected components[ABW98],[MR99]
Dec. 7Connected components[MR99]
Dec. 10Canceled 
Dec. 14Canceled 
Dec. 17Final 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. [F99] Amortisered analyse af (a,b)-træer, Rolf Fagerberg, Note, 1999.
  4. [FJKT99] Heaps and heapsort on secondary storage, R. Fadel, K. V. Jakobsen, J. Katajainen, and J. Teuhola. Theoretical Computer Science 220 (1999), 345-362
  5. [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.
  6. [KL92] I/O-complexity of comparison and permutation problems. Mikael Knuden and Kirsten Larsen. Master Thesis, DAIMI, November 1992.
  7. [S98] Random Permutations on Distributed, External and Hierarchical Memory, Peter Sanders. Information Processing Letters 56 (1998) 305-309.
  8. [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
  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. [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.
  11. [AHVV99] Efficient Bulk Operations on Dynamic R-trees, Lars Arge, Klaus Hinrichs, Jan Vahrenhold, and Jeff Vitter. In Proceedings ALENEX '99, 1999.
  12. [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.
  13. [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.
  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.

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