CS 473: Topics in Analysis of Algorithms (Fall 2003)

Announcements

• Homework 3 is due December 20, the last day of final exams.

Overview

More and more frequently, computer systems are called on to handle massive amounts of data, much more than can fit into memory. In this context, the cost of an algorithm is more aptly measured in terms of the amount of data transferred between slow memory (disks, for example) and fast memory, rather than the number of executed instructions. Similar (although somewhat less severe) issues arise in designing algorithms and data structures to exploit caches. In extreme cases, the data is not only too large to store, but also too large to read more than once.

This course will survey ongoing research into algorithms and data structures for massive data. The course material will be roughly divided into three categories:

• External-memory algorithms and data structures
• Cache-oblivious algorithms and data structures
• Stream algorithms

Despite the relative novelty of this research area, there is already more than enough material to cover three or four courses. Students are strongly encouraged to suggest topics for future lectures or discussion!

Schedule

References

Whenever possible, the title of each work links to a free online copy. Journal/proceedings data links to the publisher's official web page for the paper; an institutional subscription may be required to access the paper itself.

*Stars indicate authors who were graduate students when that paper was written.
**Double stars indicate undergraduate authors.

[AAMVV99]

Pankaj K. Agarwal, Lars Arge, T. M. Murali*, Kasturi R. Varadarajan*, and Jeffrey S. Vitter. I/O-efficient algorithms for contour-line extraction and planar graph blocking. Proc. ACM-SIAM Symposium on Discrete Algorithms, 117-126, 1999.

[ABT00]

Lars Arge, Gerth Stølting Brodal, and Laura Toma*. On external-memory MST, SSSP, andd multi-way planar graph separation. Proc. Scandinavian Workshop on Algorithms and Theory, 433-447, 2000.

[Arge95]

Lars Arge*. The buffer tree: A new technique for optimal I/O algorithms. Proc. 4th Workshop on Algorithms and Data Structures, 334-345, 1995. Lecture Notes in Computer Science 955, Springer-Verlag, Berlin.

Introduces buffer trees.

[Arge03]

Lars Arge. The buffer tree: A technique for designing batched external data structures. Algorithmica 37:1-24, 2003.

Full version of [Arge95].

[ASV99]

Lars Arge,Vasilis Samoladas*, and Jeffrey Scott Vitter. On two-dimensional indexability and optimal range search indexing. Proc. ACM Symposium on Principles of Database Systems, 346-357, 1999.

External priority search trees and 2d range trees.

[AV88]

Alok Aggarwal and Jeffrey Scott Vitter. The input/output complexity of sorting and related problems. Communications of the ACM 31(9):1116-1127, 1988.

Introduces the standard external-memory model; proves tight upper and lower bounds for searching, scanning, sorting, FFTs, matrix inversion, and other problems.

[AV96]

Lars Arge* and Jeffrey Scott Vitter. Optimal dynamic interval management in external memory. Proc. IEEE Symposium on Foundations of Computer Science, 560-569, 1996.

Introduces external interval trees and external segment trees; the main contribution is the idea of multislab lists.

[AVV95]

Lars Arge*, Darren E. Vengroff*, and Jeffrey Scott Vitter. External-memory algorithms for processing line segments in geographic information systems. Proc. ESA '95. Algorithmica, to appear.

Optimal algorithms for endpoint-dominance, red-blue segment intersection, batched planar point location, and the like, using a combination of distribution sweeping and buffer trees.

[BGVW00]

Adam Buchsbaum, Michael Goldwasser, Suresh Venkatasubramanian, and Jeffrey R. Westbrook. On external-memory graph traversal. Proc. ACM-SIAM Symposium on Discrete Algorithms, 859-860, 2000.

[BM72]

Rudolf Bayer and Edward M. McCreight. Organization and maintenance of large ordered indexes. Acta Informatica 1:173-189, 1972.

Introduces B-trees.

[CGGTVV95]

Yi-Jen Chiang*, Michael T. Goodrich, Eddie F. Grove, Roberto Tamassia, Darren E. Vengroff*, and Jeffrey S. Vitter. External-memory graph algorithms. Proc. ACM-SIAM Symposium on Discrete Algorithms, 139--149, 1995.

[GTVV93]

Michael T. Goodrich, J.-J. Tsay*, Darren E. Vengroff*, and Jeffrey Scott Vitter. External-memory computational geometry. Proc. IEEE Symposium on Foundations of Computing, 714-723, 1993.

Introduces distribution sweeping.

[KnuthIII]

Donald E. Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, second edition. Addison-Wesley, 1998.

Chapter 5.4 discusses external sorting in Knuth's usual exquisite/excruciating detail, but not in our standard external-memory model. Chapters 6.2.3 and 6.2.4 discuss B-trees and their variants: B⁺-trees, B*-trees, (a,b)-trees, etc.

[KRVV96]

Paris C. Kannelakis, Sridhar Ramaswamy, Darren E. Vengroff*, and Jeffrey Scott Vitter. Indexing for data models with constraints and classes. Journal of Computer and System Sciences 52(3):589-612, 1996.

Introduces metablock trees, which are used as underflow structures in external segment and interval trees in [AV96].

[KS96]

Vijay Kumar and Eric Schwabe. Improved algorithms and data structures for solving graph problems in external memory. Proc. IEEE Symposium on Parallel and Distributed Processing, 167-177, 1996.

[Mehlhorn84]

Kurt Mehlhorn. Data Structures and Algorithms 1: Sorting and Searching. EATCS Monographs on Theoretical Computer Science, Springer-Verlag, 1984.

Chapter III 5.2 describes and analyzes (a,b)-trees.

[MR99]

Kamesh Munagala and Abhiram Ranade. I/O-complexity of graph algorithms. Proc. ACM-SIAM Smposium on Discrete Algorithms, 687-694, 1999.

Administrivia

Instructor: Jeff Erickson (jeffe@cs.uiuc.edu)

Tentative office hours: Thursday 1:30-3:30, at Green Street Coffee House

Course website: http://www.cs.uiuc.edu/~jeffe/teaching/473/

Course newsgroup: uiuc.class.cs473

 

Prerequisites:

This is an advanced graduate-level algorithms class, aimed primarily (but not exclusively!) at students interested in algorithms research. Students are expected to have a solid grounding in basic algorithm design and analysis techniques. A minimal prerequisite is an introductory graduate-level algorithms course like CS 373. Mathematically and/or algorithmically mature undergraduates are welcome.

 

Coursework:

Grades will be based on 4-5 homeworks and a take-home final. Students can substitute a survey/implementation/research project for the take-home final with my permission and the understanding that my standards for course projects are unreasonable.

 

Reading Material:

There is no textbook for this class. The lecture material will be taken almost entirely from recent conference and journal papers; I will provide pointeds to electronic copies of these papers whenever possible. However, the following survey papers are highly recommended:

• Lars Arge. External memory data structures. Handbook of Massive Data Sets. Kluwer, 2002.
• Lars Arge. External-memory algorithms with applications in geographic information systems. Algorithmic Foundations of Geographic Information Systems, 1997.
• Erik D. Demaine. Cache-oblivious algorithms and data structures. Lecture Notes from the EEF Summer School on Massive Data Sets, 2002.
• S. Muthukrishnan. Data streams: Algorithms and applications. Preprint, 2003.
• Jeff Vitter. External-memory algorithms and data structures: Dealing with massive data. ACM Computing Surveys, 33(2):209-271, 2001. [Official version from ACM]

See also course syllabi/notes/slides by Lars Arge (I/O efficient algorithms), Gerth Stølting Brodal (External memory algorithms and data structures), S. Muthukrishnan and Graham Cormode (Seminar on processing massive data sets), and the EEF summer school on massive data sets.