UNIVERSITY OF AARHUS
DEPARTMENT OF COMPUTER SCIENCE

Pensum: External Memory Algorithms and Data Structures, Fall 2001

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. Sect. 1-3.2
2.[KL92] I/O-complexity of comparison and permutation problems. Mikael Knuden and Kirsten Larsen. Master Thesis, DAIMI, November 1992. Sect. 1-3.2,4.1-4.2
3.[BF00] Amortized Analysis of (a,b)-Trees, Gerth Stølting Brodal and Rolf Fagerberg, Note, 2000. All
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. Sect. 1-2,4,6-9
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. Sect. 1-2.1
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. All
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. All
8.[AHVV99] Efficient Bulk Operations on Dynamic R-trees, Lars Arge, Klaus Hinrichs, Jan Vahrenhold, and Jeff Vitter. In Proceedings ALENEX '99, 1999. All
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. All
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 Sect. 1,2.2.1,3.1-3.3.2,4-5
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. Sect. 1-3,5
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. Sect. 1-4,6
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. Sect. 5
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. Sect. 1-2
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. Sect. 1-4.3,4.5-7
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. All
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. All
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. All

Projects






StudentGerth Stølting BrodalRolf Fagerberg