Literature

All download links should work through the ETH domain, and some from anywhere.
In case you are not allowed to download, you might want to google the title of the paper and find a copy of paper in authors' pages.

The papers are listed in the alphabetical order of the keys.

---

Back to the course page

---

Papers discussed in the lectures

[AKL93]

Lars Arge, Mikael Knudsen and Kirsten Larsen.
A General Lower Bound on the I/O-Complexity of Comparison-Based Algorithms.
Proceedings of Workshop on Algorithms and Data Structures (WADS'93),
Lecture Notes in Computer Science 709 (1993) 83-94.
(Download via Lars Arge's page)

[AL93]

Arne Andersson and Tony W. Lai.
Fast updating of well-balanced trees. Proceedings of 2nd Scandinavian Workshop on Algorithm Theory (SWAT'90),
Lecture Notes in Computer Science 447 (1990) 111-121.
(Download via Arne Andersson's page)

[Arg03]

Lars Arge.
The Buffer Tree: A Techinique for Designing Batched External Data Structures.
Algorithmica 37 (2003) 1-24.
(Download via SpringerLink)

[ASV99]

Lars Arge, Vasilis Samoladas, and Jeffrey S. Vitter.
On Two-Dimensional Indexability and Optimal Range Search Indexing.
Proceedings of 18th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS'99), 346-357, 1999.
(Download via the ACM Digital Library)

[AV88]

Alok Aggarwal and Jeffrey S. Vitter.
The Input/Output Complexity of Sorting and Related Problems.
Communications of the ACM 31 (1988) 1116-1127.
(Download via the ACM Digitral Library)

[BBFG+03]

Michael A. Bender, Gerth Stølting Brodal, Rolf Fagerberg, Dongdong Ge, Simai He, Haodong Hu, John Iacono and Alejandro López-Ortiz.
The Cost of Cache-Oblivious Searching.
Proceedings of 44th Foundations of Computer Science (FOCS 2003), 271-282, 2003.
(Download via Dondong Ge's webpage)
(Download via Haodong Hu's webpage)

[BF00]

Gerth Stølting Brodal and Rolf Fagerberg.
Amortized Analysis of (a,b)-Trees.
Manuscript, 2000.
(Download via Gerth Brodal's page)

[BF02]

Gerth Stølting Brodal and Rolf Fagerberg.
Cache Oblivious Distribution Sweeping.
Proceedings of 29th International Colloquium on Automata, Languages, and Programming (ICALP 2002),
Lecture Notes in Computer Science 2380 (2002) 426-438.
(Download via SpringerLink)

[BF03]

Gerth Stølting Brodal and Rolf Fagerberg.
On the Limits of Cache-Obliviousness.
Proceedings of 35th Annual ACM Symposium on Theory of Computing (STOC 2003), 307-315, 2003.
(Download via ACM Digital Library)

[BFJ02]

Gerth Stølting Brodal, Rolf Fagerberg and Riko Jakob.
Cache-Oblivious Search Trees via Trees of Small Height.
Proceedgins of 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002), 39-48, 2002.
(Download via ACM Digital Library)

[FLPR99]

Matteo Frigo, Charles E. Leiserson, Harald Prokop, and Sridhar Ramachandran.
Cache-Oblivious Algorithms.
Proceedings of 40th Annual Symposium on Foundations of Computer Science (FOCS'99), 1999, 285-297.
(Download via IEEE Xplore)

[HK81]

Jia-Wei Hong and H.T. Kung.
I/O-complexity: The red blue pebble game.
Proceedings of 13th Annual ACM Symposium on Theory of Computing (STOC'81), 326-333, 1981.
(Download via ACM Digital Library)

[HMRT86]

Kurt Hoffmann, Kurt Mehlhorn, Pierre Rosenstiehl and Robert E. Tarjan.
Sorting Jordan Sequences in Linear Time Using Level-Linked Search Trees.
Information and Control 68 (1986) 170-184.

[JLN02]

Lars Jacobsen, Kim S. Larsen and Morten N. Nielsen.
On the Existence and Construction of Non-Extreme (a,b)-Trees.
Information Processing Letters 84 (2002) 69-73.
(Download via ScienceDirect)

[NW99]

Jürg Nievergelt and Peter Widmayer.
Spatial data structures: Concepts and design choices.
In: Jörge-Rüdiger Sack and Jorge Urrutia, editors,
Handbook of Computational Geometry, 1999, Chapter 17, 725-764.

[PMSS04]

Kerttu Pollari-Malmi and Eljas Soisalon-Soininen.
Concurrency Control and I/O-Optimality in Bulk Insertion.
Proceedings of 11th Symposium on String Processing and Information Retrieval (SPIRE 2004),
Lecture Notes in Computer Science 3246 (2004) 161-170.
(Download via SpringerLink)

[Pro99]

Harald Prokop.
Cache-Oblivious Algorithms.
Master's Thesis, MIT, 1999.
(Download via Cilk project's webpage)

[ST85]

Daniel D. Sleator and Robert E. Tarjan.
Amortized Effciency of List Update and Paging Rules.
Communications of the ACM, 28:202-208, 1985.
(Download via ACM Digital Library)

---

Some survey articles and volumes

[Arg97]

Lars Arge.
External-Memory Algorithms with Applications in Geographic Information Systems.
Algorithmic Foundations of Geographic Information Systems,
Lecture Notes in Computer Science 1340 (1997) 213-254.
(Download via Lars Arge's page)

[MSS03]

Urlich Meyer, Peter Sanders and Jop Sibeyn, editors.
Algorithms for Memory Hierarchies: Advanced Lectures,
Lecture Notes in Computer Science 2625 (2003).
(Download via SpringerLink)

[Vit01]

Jeffrey S. Vitter.
External Memory Algorithms and Data Structures: Dealing with Massive Data.
ACM Computing Surveys 33 (2001) 209-271.
(Download via the ACM Digital Library)

---

Back to the course page

---

Last modified:Mon Mar 21 00:14:50 2005 by Yoshio Okamoto.