CPS 238 I/O-Efficient Algorithms

Summary of Lectures and List of Material


 
Lec.
Date
Topic
Reading
0
Sep 4
 Outline of course 
 -
1-2
Sep 6
 Intro: I/O-model and fundamental bounds
Sorting and Searching: External sorting, B-trees		 [AV] sec 3+5
[Agis] sec  1, 2, 3.1-3.2, [AL]
[Mehlhorn], [Ads] sec 2.0
3-4
Sep 13
 Sorting and Searching: Buffer-trees, lower bounds [Agis] sec 3.3, [Abuffer] sec 1-4, [Alower]
[AV] (only stuff on sorting/permuting lower bound)
5-6
Sep 20
 Graph problems: List ranking, algorithms on trees. [CGGTVV], sec 3-6, [Abuffer] sec 4.1
7-8
Sep 27
 Graph problems: Depth-First and Breadth-First Search [CGGTVV], sec 7, [BGVW], [MR] sec 5.1. 3.1
9-10
Oct 4
 Graph problems: Minimal Spanning Tree,
Shortest paths (tournement tree)		 [ABT] sec 2. (note on vertex contraction later)
[KS] sec 3.
11-12
Oct 11
 Graph problems: Shortest paths, discussion of other results,
lower bounds (model discussion and SPN, CC, list ranking bounds)		 [KS] sec 5.2,  [T], (review of [ABW])
[CGGTVV] sec. 2, [Aobbd] sec 2.3-lemma 2
(review of [MR] sec 2-4, [AKL] sec 1-4])
13-14
Oct 18
 Graph problems: Graph blocking
Batched geometric problems: Distribution sweeping,
external segment trees, batched filtering		 [NGV]
[Agis] sec 4.1-4.2. [GTVV] sec 2
15-16
Oct 25
 Batched geometric problems: External extended segment trees
and fractional cascading		 [AVV] sec 1-2, [Agis] 4.3.1-4.3.2
-
Nov 1
Cancelled
- 
17-18
Nov 8
 Batched geometric problems: Overview of results (line segment
intersection, convex hull, randomized algorithms), lower bounds
Geometric searching problems: Weight-balanced and persistent
B-trees		 ([Agis] sec 4.3.3-4.4, [AVV] sec 3,
[CGGTVV], [CFMMR]sec 6, [AM] sec 1)
[Ads] sec 2.1, [AVi] sec 3.1, [BGOSW], ([VV])
18-20
Nov 15
 Geometric searching problems: External interval tree, logarithmic
method, dynamic point location		 [Ads] sec 3-4, [AVi],
[AABV] sec 1-2, [AVa] sec 1-3
-
Nov 22
Thanksgiving
 -
21-22
Nov 29
  Geometric searching problems: External priority search tree, 
external range tree, kd-B trees		 [Ads] sec 5-6, [ASV] sec 1+3-4,[AAPV]
23-24
Dec 6
  Geometric searching problems: O-tree, overview of other
worst-case and heuristic results		 [KS] sec 4, [Ads] sec 7-9, [NW]

List of Material

  1. [AV] The Input/Output Complexity of Sorting and Related Problems. A. Aggarwal and J. Vitter. CACM 31 (9), 1988.
  2. [Agis] External-Memory Algorithms with Applications in Geographic Information Systems, L. Arge. In Algorithmic Foundations of GIS, M. van Kreveld, J. Nievergelt, T. Roos, and P. Widmayer (Eds.), Springer, 1997.
  3. [AL] External partition element finding, Lecture notes by L. Arge and M. G. Lagoudakis.
  4. [Mehlhorn] Data Structures and Algorithms 1: Sorting and Searching. K. Mehlhorn, EATCS Monographs on Theoretical Computer Science, Springer-Verlag, 1984. Subset of Chapter III 5.2 on (a,b)-trees (and balanced trees) pages 187-206 and 212-222.
  5. [Ads] External Memory Data Structures. L. Arge, chapter to appear in Handbook of Massive Data Sets, J. Abello, P. M. Pardalos, and M. G. C. Resende (Eds.), Kluwer Academic Publishers, 2001.
  6. [Abuffer] The Buffer Tree: A New Technique for Optimal I/O-Algorithms. L. Arge. Full version of paper in Proc. WADS'95.
  7. [Alower] Lower bound on External Permuting/Sorting, Lecture note by L. Arge.
  8. [CGGTVV] External-Memory Graph Algorithms. Y-J. Chiang, M. T. Goodrich, E.F. Grove, R. Tamassia. D. E. Vengroff, and J. S. Vitter. Proc. SODA'95.
  9. [BGVW] On External Memory Graph Traversal. A.L. Buchsbaum, M. Goldwasser, S. Venkatasubramanian, J.R. Westbrook, Proc. SODA'00.
  10. [MR] I/O-Complexity of Graph Algorithms. K. Munagala and A. Ranade. Proc. SODA'99.
  11. [ABT] On External-Memory MST, SSSP and Multi-Way Planar Graph Separation. L. Arge, G. S. Brodal, and Laura Toma. Proc. SWAT'00.
  12. [KS] Improved Algorithms and Data Structures for Solving Graph Problems in External Memory. V. Kumar and E.J. Schwabe. Proc. SPDP'96.
  13. [T] External Memory Graph Algorithms and Application (chapter 2). L. Toma. Preliminary exam document, 2001.
  14. [ABW] A functional Approach to External Graph Algorithms. J. Abello, A.L. Buchsbaum, and J.R. Westbrook. Proc. ESA'98.
  15. [Aobbd] The I/O-Complexity of Ordered Binary-Decision Diagarm Manipulation. L. Arge. Full version of paper in Proc. ISAAC'95.
  16. [AKL] A General Lower Bound on the I/O-Complexity of Comparison-based Algorithms. L. Arge, M. Knudsen, and K. Larsen, Full version of paper in Proc. WADS'93.
  17. [NGV] Blocking for External Graph Searching. M. Nodine, M. Goodrich, and J. Vitter. Algorithmica, 16: 181-214, 1996.
  18. [GTVV] External-Memory Computational Geometry. M.T. Goodrich, J-J. Tsay, D.E. Vengroff, and J.S. Vitter. Proc. FOCS'93.
  19. [AVV] External-Memory Algorithms for Processing Line Segments in Geographic Information Systems. L. Arge, D.E. Vengroff and J.S. Vitter. Algorithmica  (to appear), extended abstract in Proc. ESA'95.
  20. [CFMMR] Randomized External-Memory Algorithms for Line Segment Intersection and other Geometric Problems. A. Crauser, P. Ferragina, K. Mehlhorn, U. Meyer and E. Ramos. Intl. Jour. of Computational Geometry and Applications, 11(3): 305-337, 2001
  21. [AM] On showing lower bounds for external-memory computational geometry problems. L. Arge and P.B. Miltersen. In External Memory Algorithms and Visualization, J. Abello and J. S. Vitter (Eds.), American Mathematical Society, 1998.
  22. [AVi] Optimal Dynamic Interval Management in External Memory. L. Arge and J.S. Vitter. Full version of paper in Proc. STOC'96.
  23. [BGOSW] An Asymptotically Optimal Multiversion B-tree. B. Becker, S. Gschwind, T. Ohler, B. Seeger, and P. Widmayer. The VLDB Journal, 5:264-275, 1996.
  24.  [VV] An Efficient Multiversion Access Structure. P.J. Varman and R.M. Verma. IEEE Trans. on Knowledge and Data Engineering, 9(3): 391-409, 1997.
  25. [AABV] I/O-Efficient Dynamic Point Location in Monotone Planar Subdivisions. P.K. Agarwal, L. Arge, G.S. Brodal, and J.S. Vitter. Proc. SODA'99.
  26. [AVa] I/O-Efficient Dynamic Planer Point Location. L. Arge and J. Vahrenhold. Proc. SoCG'00.
  27. [ASV] On Two-Dimensional Indexability and Optimal Range Search Indexing. L. Arge, V. Samoladas, and J. S. Vitter. Proc. PODS'99.
  28. [AAPV] A Framework for Index Bulk Loading and Dynamization. P. Agarwal, L. Arge, O. Procopiuc, and L. Arge. Proc. ICALP'01.
  29. [KS] Optimal Dynamic Range Searching in Non-replicating Index Structures. K.V.R Kanth and A. Singh. Proc. ICDT'99.
  30. [NW] Spatial Data Structures: Concepts and Design Choices. J. Nievergelt and P. Widmayer. In Algorithmic Foundations of GIS, M. van Kreveld, J. Nievergelt, T.

    31.        Roos, and P. Widmayer (Eds.), Springer, 1997.
Lars Arge
Fri Dec 7, 2001