Princeton University
Computer Science Department

Computer Science 598E
Advanced Topics in Computer Science:
Cool Systems Ideas: Inspirations from Theory

Kai Li

Spring 2005

Course Summary

This goal of this graduate seminar is to identifying systems research opportunities that use practical theory results.

Students who take this course can consider it as a "crossover" seminar between systems and theory. We will be reading and discussing some selected papers in systems whose designs are heavily influenced by theory results and some in theory whose ideas are promising for designing future systems. The topics being considered include storage systems, similarity searches and data explorations. When reading theory papers, we will take a systems approach: focusing on data structures, algorithms and properties, not on how to prove the properties. We plan to explore several kinds of data including images, audio data, microarray genomic data, time series data, and network data.

Students who take this course for credits are required to present a selected paper and work on a small research project. Students can work individually or in teams. Several faculty members and outside researchers will be invited to give lectures in this seminar.

The first meeting time is 1:30pm in room 301.

Tentative Reading List and Schedule

Week 1 (2/5):

Week 2 (2/11): Fingerprinting and Systems (William Josephson)
        Lecture notes

Week 3 (2/18): Resemblance, Containment, and Min-Wise Permutations (Dr. Andrei Broder, IBM Watson)
        Lecture Notes

Week 4 (2/25): Music Search and Audio Similarity (Prof. Perry Cook)
        Lecture notes

Week 5 (3/4): Dimension Reduction Techniques (Prof. Moses Charikar)
        Lecture notes

Week 6 (3/11): Bloom Filters and Applications (Elliott Karpilovsky)
        Lecture notes

Week 7 (3/25): Introduction to Genomic Data (Prof. Olga Troyanskaya, Matt Hibbs)
        Lecture notes (Troyanskaya), Lecture notes (Hibbs)

Week 8 (4/1): Time Series Data (Zhe Wang)
        Lecture notes

Week 9 (4/8): Image Data Similarity Search (Frank Battagua)
        Lecture notes

Week 10 (4/15): Trip to DB/IR day at Columbia University

Week 11 (4/22) Indexing for Similarity Search (Christine Lv)
        Lecture notes

Week 11 (4/29): Network Data Analysis using Sketches (Haakon Larsen)

Week 12 (5/9): Project presentations

Administrative Information

Regular class meets: F 1:30-4:20, Room: 301

Professor: Kai Li - 321 CS Building - 258-4637

Graduate Coordinator: Melissa Lawson - 310 CS Building - 258-5387

Teaching Assistants: TBA