CAP 6930: Approximate Query Processing

Approximate Query Processing is a graduate course geared toward Ph.D level students. The goal of the class is to expose students to the topic of approximation theory and to develop research skills like:

In the course we will explore analysis technique to design and analyze approximation schemes such as histograms, wavelets, sampling and sketches. While the class has a database motivation, the material should be useful for any student that is conducting/planning to conduct research that involves approximations.


Homework Assignments

Lecture Notes

Reading Material

Grading Policy

The final grade in the class will be based on:

There will be no final exam or mid-term.


For the homeworks you are allowed to discuss the solutions in groups but you have to write the answers alone. Please specify on the submitted homework what are the students you collaborated with.


The project will consist in applying the techniques we discuss in class to some research problem. If you are working on a problem that would benefit from such techniques as part of your research, you are more than welcomed to hate that problems as your research topic. Otherwise, I will help you identify a topic that is appropriate. Group projects are possible.

The actual project will consists in: