Course material

Handouts from lectures

Erik Demaine: Data Structures

Erik Demaine: Computational Geometry

List of Literature

Below is a list of literature relevant to the MADALGO Summer School on Cache-Oblivious Algorithms. A subset of the papers will be handed out during the summer school. The links below are to copies of the papers at the authors or publishers web pages - in some cases with limited access. Local copies of all papers are available to the participants of the summer school (password protected).

References

    Surveys

  1. [D02] Cache-Oblivious Algorithms and Data Structures. Erik Demaine. Lecture Notes from the EEF Summer School on Massive Data Sets, Lecture Notes in Computer Science, BRICS, University of Aarhus, Denmark, June 27-July 1, 2002, to appear.
  2. [B04] Cache-Oblivious Algorithms and Data Structures. Gerth Stølting Brodal. In Proc. 9th Scandinavian Workshop on Algorithm Theory, volume 3111 of Lecture Notes in Computer Science, pages 3-13. Springer Verlag, Berlin, 2004.
  3. [ABF05] Cache-Oblivious Data Structures. Lars Arge, Gerth Stølting Brodal, and Rolf Fagerberg. In Handbook of Data Structures and Applications, Dinesh Mehta and Sartaj Sahni (Edt.), 27 pages. CRC Press, 2005.
  4. [K03] Cache Oblivious Algorithms. Piyush Kumar. Updated version of chapter appearing in: Algorithms for Memory Hierarchies, volume 2625 of Lecture Notes in Computer Science, pages 193-212. Springer Verlag, Berlin, 2003.

    Model and Sorting

  5. [AV88] The Input/Output Complexity of Sorting And Related Problems. Alok Aggarwal and Jeffrey Scott Vitter. Communications of the ACM, 31(9):1116-1127, September 1988.
  6. [FLPR99] Cache-Oblivious Algorithms. Matteo Frigo, Charles E. Leiserson, Harald Prokop, and Sridhar Ramachandran. In Proc. 40th Annual Symposium on Foundations of Computer Science, 285-297, 1999.
  7. [P99] Cache-Oblivious Algorithms. Harald Prokop. Master's thesis, Massachusetts Institute of Technology, Cambridge, MA, June 1999.
  8. [BFM05] Cache-Aware and Cache-Oblivious Adaptive Sorting. Gerth Stølting Brodal, Rolf Fagerberg, and Gabriel Moruz. In Proc. 32nd International Colloquium on Automata, Languages, and Programming, volume 3580 of Lecture Notes in Computer Science, pages 576-588. Springer Verlag, Berlin, 2005.
  9. [BFV07] Engineering a Cache-Oblivious Sorting Algorithm. Gerth Stølting Brodal, Rolf Fagerberg, and Kristoffer Vinther. In ACM Journal of Experimental Algorithmics, Special Issue of ALENEX 2004, volume 12(Article No. 2.2), 23 pages, 2007.
  10. [LFN02] A Comparison of Cache Aware and Cache Oblivious Static Search Trees Using Program Instrumentation. Richard E. Ladner, Ray Fortna, and Bao-Hoang Nguyen. Experimental Algorithmics, volume 2547 of Lecture Notes in Computer Science, pages 78-92. Springer Verlag, Berlin, 2002.
  11. [dT08] Cache-Oblivious Selection in Sorted X+Y Matrices Mark de Berg and Shripad Thite. Manuscript, March 2008.
  12. [FFFM05] Cache-Oblivious Comparison-Based Algorithms on Multisets. Arash Farzan, Paolo Ferragina, Gianni Franceschini, and J. Ian Munro In Proc. 13th Annual European Symposium on Algorithms, volume 3669 of Lecture Notes in Computer Science, pages 305-316. Springer Verlag, Berlin, 2005.
  13. [F04] Proximity Mergesort: optimal in-place sorting in the cache-oblivious model. Gianni Franceschini. In Proc. 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 291-299, 2004.

    Lower Bounds

  14. [BF03a] On the Limits of Cache-Obliviousness. Gerth Stølting Brodal and Rolf Fagerberg. In Proc. 35th Annual ACM Symposium on Theory of Computing, pages 307-315, 2003.
  15. [S07] On the Limits of Cache-Oblivious Matrix Transposition. Francesco Silvestri. Trustworthy Global Computing, volume 4661 of Lecture Notes in Computer Science, pages 233-243. Springer Verlag, Berlin, 2007.
  16. [BBFGHHIL03] The Cost of Cache-Oblivious Searching. Michael A. Bender, Gerth Stølting Brodal, Rolf Fagerberg, Dongdong Ge, Simai He, Haodong Hu, John Iacono, and Alejandro Lóez-Ortiz. In Proc. 44th Annual Symposium on Foundations of Computer Science, pages 271-282, 2003.
  17. [BF03b] Lower Bounds for External Memory Dictionaries. Gerth Stølting Brodal and Rolf Fagerberg. In Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 546-554, 2003.

    Data Structures

  18. [BDF05] Cache-Oblivious B-Trees. Michael A. Bender, Erik D. Demaine, and Martin Farach-Colton. SIAM Journal of Computing 35(2): 341-358 (2005).
  19. [BDIW04] A Locality-Preserving Cache-Oblivious Dynamic Dictionary. Michael A. Bender, Ziyang Duan, John Iacono, and Jing Wu. J. Algorithms 53(2): 115-136 (2004).
  20. [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.
  21. [BCR02] Exponential Structures for Efficient Cache-Oblivious Algorithms. Michael A. Bender, Richard Cole, and Rajeev Raman. In Proceedings of the 29th International Colloquium on Automata, Languages and Programming, Volume 2380 of Lecture Notes In Computer Science, pages 195-207. Springer Verlag, Berlin, 2002.
  22. [BFGK05] Concurrent Cache-Oblivious B-Trees. Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Bradley C. Kuszmaul. In Proc. 27th Annual ACM Symposium on Parallel Algorithms and Architectures, pages 228-237, 2005.
  23. [BFFFKN07] Cache-Oblivious Streaming B-Trees. Michael A. Bender, Martin Farach-Colton, Jeremy T. Fineman, Yonatan R. Fogel, Bradley C. Kuszmaul, and Jelani Nelson. In Proc. 29th Annual ACM Symposium on Parallel Algorithms and Architectures, pages 81-92, 2007.
  24. [BCDFC02] Scanning and Traversing: Maintaining Data for Traversals in a Memory Hierarchy. Michael A. Bender, Richard Cole, Erik D. Demaine, and Martin Farach-Colton. In Proceedings of the 10th Annual European Symposium on Algorithms, volume 2461 of Lecture Notes in Computer Science, pages 139-151, Rome, Italy, September 2002.
  25. [ABDFMRT03] Efficient Tree Layout in a Multilevel Memory Hierarchy. Stephen Alstrup, Michael A. Bender, Erik D. Demaine, Martin Farach-Colton, J. Ian Munro, Theis Rauhe, and Mikkel Thorup. Manuscript, December 2003.
  26. [BKTW07] Optimal Cache-Oblivious Mesh Layouts, Michael A. Bender, Bradley C. Kuszmaul, Shang-Hua Teng, Kebin Wang. CoRR abs/0705.1033: (2007)
  27. [ABDHM07] An Optimal Cache-Oblivious Priority Queue and Its Application to Graph Algorithms. Lars Arge, Michael A. Bender, Erik D. Demaine, Bryan Holland-Minkley, and J. Ian Munro. SIAM Journal of Computing 36(6): 1672-1695, 2007.
  28. [BF02a] Funnel Heap - A Cache Oblivious Priority Queue. Gerth Stølting Brodal and Rolf Fagerberg. In Proc. 13th Annual International Symposium on Algorithms and Computation, volume 2518 of Lecture Notes in Computer Science, pages 219-228. Springer Verlag, Berlin, 2002.
  29. [FG03a] Optimal Cache-Oblivious Implicit Dictionaries. Gianni Franceschini and Roberto Grossi. In Proc. 30th International Colloquium on Automata, Languages, and Programming, volume 2719 of Lecture Notes in Computer Science, pages 316-331. Springer Verlag, Berlin, 2003.
  30. [FG03b] Optimal Worst-Case Operations for Implicit Cache-Oblivious Search Trees. Gianni Franceschini and Roberto Grossi. In Proc. 8th International Workshop on Algorithms and Data Structures, volume 2748 of Lecture Notes in Computer Science, pages 114-126. Springer Verlag, Berlin, 2003.

    Graph Algorithms

  31. [JZ05] Cache-Oblivious Planar Shortest Paths. Hema Jampala and Norbert Zeh. In Proc. 32nd International Colloquium on Automata, Languages, and Programming, volume 3580 of Lecture Notes in Computer Science, pages 563-575. Springer Verlag, Berlin, 2005.
  32. [ALZ07] A Faster Cache-Oblivious Shortest-Path Algorithm for Undirected Graphs with Bounded Edge Lengths. Luca Allulli, Peter Lichodzijewski, and Norbert Zeh. In Proc. 18th Annual ACM-SIAM Symposium on Discrete Algorithms, 910-919, 2007
  33. [BFMZ04] Cache-Oblivious Data Structures and Algorithms for Undirected Breadth-First Search and Shortest Paths. Gerth Stølting Brodal, Rolf Fagerberg, Ulrich Meyer, and Norbert Zeh. In Proc. 9th Scandinavian Workshop on Algorithm Theory, volume 3111 of Lecture Notes in Computer Science, pages 480-492. Springer Verlag, Berlin, 2004.
  34. [CR04] Cache-Oblivious Shortest Paths in Graphs Using Buffer Heap. Rezaul Alam Chowdhury and Vijaya Ramachandran. In Proc. 26th Annual ACM Symposium on Parallel Algorithms and Architectures, pages 245-254, 2004

    Computational Geometry

  35. [BF02b] Cache Oblivious Distribution Sweeping. Gerth Stølting Brodal and Rolf Fagerberg. In Proc. 29th International Colloquium on Automata, Languages, and Programming, volume 2380 of Lecture Notes in Computer Science, pages 426-438. Springer Verlag, Berlin, 2002.
  36. [AADH03] Cache-Oblivious Data Structures for Orthogonal Range Searching. Pankaj K. Agarwal, Lars Arge, Andrew Danner, and Bryan Holland-Minkley. In Proc. 19th Annual ACM Symposium on Computational Geometry, pages 237-245, 2003.
  37. [ABFL05] Cache-Oblivious Planar Orthogonal Range Searching and Counting. Lars Arge, Gerth Stølting Brodal, Rolf Fagerberg, and Morten Laustsen. In Proc. 21st Annual ACM Symposium on Computational Geometry, pages 160-169, 2005.
  38. [AZ06] Simple and Semi-Dynamic Structures for Cache-Oblivious Planar Orthogonal Range Searching. Lars Arge and Norbert Zeh. In Proc. 22nd Annual ACM Symposium on Computational Geometry, pages 158-166, 2006.
  39. [AdH05] Cache-Oblivious R-Trees. Lars Arge, Mark de Berg, and Herman J. Haverkort. In Proc. 21st Annual ACM Symposium on Computational Geometry, pages 170-179, 2005.
  40. [AF07] Cache-Oblivious Output-Sensitive Two-Dimensional Convex Hull Peyman Afshani and Arash Farzan. In Proceedings of the 19th Annual Canadian Conference on Computational Geometry, pages 153-155, 2007.

    String Algorithms

  41. [BF06] Cache-Oblivious String Dictionaries. Gerth Stølting Brodal and Rolf Fagerberg. In Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 581-590, 2006.
  42. [BFK06] Cache-Oblivious String B-Trees. Michael A. Bender, Martin Farach-Colton, and Bradley C. Kuszmaul. In Proc. 25th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pages 233-242, 2006
  43. [FPP06] External String Sorting: Faster and Cache-Oblivious. Rolf Fagerberg, Anna Pagh, and Rasmus Pagh. In Proc. 3rd Annual Symposium on Theoretical Aspects of Computer Science, volume 3884 of Lecture Notes in Computer Science, pages 68-79. Springer Verlag, Berlin, 2006.
  44. [KS03] Simple Linear Work Suffix Array Construction. Juha Kärkkäinen and Peter Sanders. In Proc. 30th International Colloquium on Automata, Languages, and Programming, volume 2719 of Lecture Notes in Computer Science, pages 943-955. Springer Verlag, Berlin, 2003.
  45. [HLSTV07] Cache-Oblivious Index for Approximate String Matching Wing-Kai Hon, Tak-Wah Lam, Rahul Shah, Siu-Lung Tam, and Jeffrey Scott Vitter. In Proc. 18th Annual Symposium on Combinatorial Pattern Matching, volume 4580 of Lecture Notes in Computer Science, pages 40-51. Springer Verlag, Berlin, 2007.
  46. [FGGSV08] On searching compressed string collections cache-obliviously. Paolo Ferragina, Roberto Grossi, Ankur Gupta, Rahul Shah, and Jeffrey Scott Vitter In Proc. 27th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pages 181-190, 2008.

    Dynamic Programming and Numerical Computations

  47. [CR06a] Cache-Oblivious Dynamic Programming. Rezaul Alam Chowdhury and Vijaya Ramachandran. In Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 591-600, 2006.
  48. [CR06b] The Cache-Oblivious Gaussian Elimination Paradigm: Theoretical Framework and Experimental Evaluation. Rezaul Alam Chowdhury and Vijaya Ramachandran: In Proc. 28th Annual ACM Symposium on Parallel Algorithms and Architectures, page 236, 2006.
  49. [CR07] The Cache-Oblivious Gaussian Elimination Paradigm: Theoretical Framework, Parallelization and Experimental Evaluation. Rezaul Alam Chowdhury and Vijaya Ramachandran. In Proc. 29th Annual ACM Symposium on Parallel Algorithms and Architectures, pages 71-80, 2007.
  50. [BBFJV07] Optimal Sparse Matrix Dense Vector Multiplication in the I/O-Model. Michael A. Bender, Gerth Stølting Brodal, Rolf Fagerberg, Riko Jacob, and Elias Vicari. In Proc. 19th ACM Symposium on Parallelism in Algorithms and Architectures, pages 61-70, 2007.
  51. [R07] Cache-Oblivious Computation: Algorithms and Experimental Evaluation. Vijaya Ramachandran. ICCTA 2007: 20-26.
  52. [BDP08] Subquadratic Algorithms for 3SUM. Ilya Baran, Erik D. Demaine, and Mihai Pǎtraşcu. Algorithmica, volume 50, number 4, April 2008, pages 584596. Special issue of selected papers from the 9th Workshop on Algorithms and Data Structures, 2005.
  53. [FS07] The memory behavior of cache oblivious stencil computations. Matteo Frigo and Volker Strumpen. The Journal of Supercomputing, Volume 39, Number 2, pages 93-112, 2007.
  54. [TFS07] Cache oblivious algorithms for nonserial polyadic programming. Guangming Tan, Shengzhong Feng, and Ninghui Sun. The Journal of Supercomputing, Volume 39, Number 2, pages 227-249, 2007.

    Parallel Algorithms for Private-Cache

  55. [AGNS08] Fundamental Parallel Algorithms for Private-Cache Chip Multiprocessors. Lars Arge, Michael T. Goodrich, Michael Nelson, and Nodari Sitchinava. In Proc. 20th ACM Symposium on Parallelism in Algorithms and Architectures, pages 197-206, 2008.
  56. [AGS08] Parallel External Memory Graph Algorithms. Lars Arge, Michael T. Goodrich, and Nodari Sitchinava. Manuscript, 2008.
MADALGO - Center for Massive Data Algorithmics, a Center of the Danish National Research Foundation / Department of Computer Science / Aarhus University