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:
- Make oral presentations
- Critical thinking
- Paper writing
- Conducting research
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.
Instructor
- Alin Dobra
Office: 474 CSE Building
Email: adobra at cise.ufl.edu
- Office Hours: Tu 10-11:30, Th 13-14:30
Homework Assignments
Lecture Notes
Reading Material
- Introduction to Probability
Theory and Statistics (this is an appendix from my Ph.D thesis)
- Wen-Chi Hou,
Wen-Chi Hou,
Gultekin Ozsoyoglu, Statistical estimators for relational algebra expressions
- Frank Olken, Doron Rotem, Random Sampling from Databases
- Jeffery Vitter Random sampling with a reservoir
- S. Chaudhuri, R. Motwani and N. Narasayya,
On Random Sampling over Joins
- Phillip B. Gibbons, Yossi Matias
New sampling-based summary statistics for improving approximate query answers
- Sumit Ganguly, Phillip B. Gibbons, Yossi Matias,Avi Silberschatz
Bifocal sampling for skew-resistant join size estimation
- Surajit Chaudhuri, Gautam Das, Mayur Datar
Overcoming Limitations of Sampling for Aggregation Queries
- Alin Dobra Histograms Revisited PODS 2005
Grading Policy
The final grade in the class will be based on:
- 20% for class participation
- 40% for 4 homeworks spread throughout the semester
- 40% for the final project
There will be no final exam or mid-term.
Homeworks
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.
Project
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:
- Analyze a small research topic
- Write a 4-6 page paper about your research
- Give a 15 minute oral presentation of your project in class