CPS 238 I/O-Efficient Algorithms

时间：2006-12-20 来源：rwen2012

CPS 238 I/O-Efficient Algorithms

Summary of Lectures and List of Material

Go to list of material

Lec.	Date	Topic	Reading
1	Jan 8	Introduction: Hierarchical memory, I/O-bottleneck, I/O-model, fundmental bounds Sorting: Merge and distribution sort	[AV] sec 3+5 [Agis] sec 1, 2, 3.1-3.2, [AL]
2-3	Jan 15	Lower bounds: Sorting and searching Searching: B-trees,	[Mehlhorn], [Ads] sec 2.0, [Alower], [AV] (only stuff on sorting and permuting lower bounds)
4-5	Jan 22	Searching: Weight-balanced B-trees, Persistent B-trees, buffer trees	[AVi] sec 3.,1[Ads] sec 2.1, [ADT] sec 2.1, [BGOSW], [Abuffer] sec 1-4, [Agis] sec 3.3, [Ads] sec 10
-	Mar 27	Cancelled (snow)	-
6-7	Feb 5	Geometric data structures: Logarithmic method, interval tree, point location	[Ads] sec 3-4, [AVi], [ADT] sec 1-2, [AABV] sec 1-2, [AVa] sec 1-3
8-9	Feb 12	Geometric data structures: Priority search tree, range tree, kdB-tree, O-tree, overview of other results	[Ads] sec 5-6 (+7-9), [ASV] sec 1+3-4, [PAAV] 1-2, [KS] sec 4.
10-11	Feb 19	Batched geometric problems: Distribution sweeping, external segment trees, batched filtering, and fractional cascading (EPD problem)	[Agis] sec 4.1-4.3.2, [GTVV] sec 2, [AVV] sec 1-2
12-13	Feb 26	Cache-oblivious algorithms (Bryan): Model, van Emde Boas layout, funnelsort, distribution sort, Exponential trees	[FLPR] sec 1, 4-6, [BCR] sec 2.1-2.2
14-15	Mar 4	Cache-oblivious algorithms (Bryan): Priority queue, distribution sweeping, range searching, practicality	[ABDHM] sec 2, [BF] sec 2-3.1, [AADH] sec 2, [BFV]
-	Mar 11	Spring Break	-
16-17	Mar 18	Graph algorithms: List ranking, algorithms on trees	[CGGTVV], sec 3-6, [Abuffer] sec 4.1, [ABDHM] sec 3.1-3.2
18-19	Mar 25	Graph algorithms: Depth-First and Breadth-First Search	[CGGTVV], sec 7, [BGVW], [MR] sec 5.1, [ABDHM] sec 3.3
20-21	Apr 1	Graph algorithms: Minimal Spanning Tree, shortest paths	[ABT] sec 2, [KSa] sec 3, [ABDHM] sec 3.4
22-23	Apr 8	Cancelled	-
24-25	Apr 15	Graph algorithms: Shortest paths, lower bounds	[KSa] sec 5.2, [CGGTVV] sec. 2, [Aobbd] sec 2.3-lemma 2 (review of [MR] sec 2-4, [AKL] sec 1-4]) (See surveys [KM] and [TZ] for other graph results)

List of Material

[AV] The Input/Output Complexity of Sorting and Related Problems. A. Aggarwal and J. Vitter. CACM 31 (9), 1988.
[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.
[AL] External partition element finding, Lecture notes by L. Arge and M. G. Lagoudakis.
[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.
[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.
[Alower] Lower bound on External Permuting/Sorting, Lecture notes by L. Arge.
[AVi] Optimal External Memory Interval Management. L. Arge and J.S. Vitter. SIAM Journal on Computing, 32(6):1499-1508, 2003
[ADT] I/O-Efficient Point Location using Persistent B-trees. L. Arge, A. Danner, and S-M. Teh. Journal of Experimental Algorithmics, 2004 (to appear).
[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.
[Abuffer] The Buffer Tree: A Technique for Designing Batched External Data Structures. L. Arge. Algorithmica, 37:1-24, 2003.
[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.
[AVa] I/O-Efficient Dynamic Planer Point Location. L. Arge and J. Vahrenhold. Computational Geometry: Theory and Applications (to appear), 2004.
[ASV] On Two-Dimensional Indexability and Optimal Range Search Indexing. L. Arge, V. Samoladas, and J. S. Vitter. Proc. PODS'99.
[PAAV] Bkd-tree: A Dynamic Scalable kd-tree. O. Procopiuc, P.K. Agarwal, L. Arge, J.S. Vitter. Proc. SSTD'03.
[KS] Optimal Dynamic Range Searching in Non-replicating Index Structures. K.V.R Kanth and A. Singh. Proc. ICDT'99.
[GTVV] External-Memory Computational Geometry. M.T. Goodrich, J-J. Tsay, D.E. Vengroff, and J.S. Vitter. Proc. FOCS'93.
[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.
[FLPR] Cache-Oblivious Algorithms. M. Frigo, C. E. Leiserson, H. Prokop and S. Ramachandran. Proc. FOCS'99.
[BCR] Exponential Structures for Efficient Cache-Oblivious Algorithms. M. Bender, R. Cole and R. Raman. Proc. ICALP'02.
[ABDHM] Cache-Obliviosu Priority Queue and Graph Algorithm Applications. L. Arge, M. Bender, E. Demaine, B. Holland-Minkley and I. Munro. Proc. STOC'02.
[BF] Cache Oblivious Distribution Sweeping. G.S. Brodal and R. Fagerberg. Proc. ICALP'02.
[AADH] On Cache-Obliviosu Multidimensional Range Searching. P.K. Agarwal, L. Arge, A. Danner, and B. Holland-Minkley. Proc. SoCG'03.
[BFV] Engineering a Cache-Oblivious Sorting Algorithm. G.S. Brodal, R. Fagerberg and R. Vinther. Proc. ALENEX'04.
[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.
[BGVW] On External Memory Graph Traversal. A.L. Buchsbaum, M. Goldwasser, S. Venkatasubramanian, J.R. Westbrook, Proc. SODA'00.
[MR] I/O-Complexity of Graph Algorithms. K. Munagala and A. Ranade. Proc. SODA'99.
[ABT] On External-Memory MST, SSSP and Multi-Way Planar Graph Separation. L. Arge, G. S. Brodal, and Laura Toma. Journal of Algorithms, 2004 (To appear).
[KSa] Improved Algorithms and Data Structures for Solving Graph Problems in External Memory. V. Kumar and E.J. Schwabe. Proc. SPDP'96.
[Aobbd] The I/O-Complexity of Ordered Binary-Decision Diagarm Manipulation. L. Arge. Full version of paper in Proc. ISAAC'95.
[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.
[KM] Elementary Graph Algorithms in External Memory. I. Katriel and U. Meyer.
[TZ] I/O-Efficient Algorithms for Sparse Graphs. L. Toma and N. Zeh.

Lars Arge
Thu April 15, 2004