CSE 590Q: Database Seminar

Fall 2005: Recent Trends in Selectivity Estimation

Dan Suciu
Wednesdays 4:30 - 5:20,
Database Lab


Day Readings Presenter
  • Introduction + paper assignment.
  • Dan Suciu
    10/5 Histograms I

  • Yannis E. Ioannidis: The History of Histograms (abridged). VLDB, 03. (10-year award paper.).
  • Yannis E. Ioannidis: Universality of Serial Histograms. VLDB, 93. (The original paper from VLDB 93).).
  • Nilesh
  • 10/12
    Histograms II (Seminar moved to Fri 10/14, 11:30 a.m.))

  • Viswanath Poosala, Yannis E. Ioannidis, Peter J. Haas, Eugene J. Shekita: Improved Histograms for Selectivity Estimation of Range Predicates. SIGMOD, 96.
  • Ashish
  • 10/19 Statistical Models I

  • Lise Getoor, Benjamin Taskar, Daphne Koller: Selectivity Estimation using Probabilistic Models. SIGMOD, 01.
  • Nodira
  • 10/26
  • Volker Markl, Nimrod Megiddo, Marcel Kutsch, Tam Minh Tran, Peter J. Haas, Utkarsh Srivastava: Consistently Estimating the Selectivity of Conjuncts of Predicates. VLDB 05.
  • Chris
  • 11/2 Sampling I

  • Surajit Chaudhuri, Rajeev Motwani, Vivek R. Narasayya: On Random Sampling over Joins. SIGMOD, 99.
  • Shobhit
  • 11/9 Sampling II

  • Frank Olken. Random Sampling from Databases. Ph.D. Thesis, 1993. [Only Chapter 2 (lit. survey), Chapter 3 and 4 (sampling from B trees and hash tables)]
  • Ashish
  • 11/16 Approximate Query Answering

  • Joseph M. Hellerstein, Peter J. Haas, Helen J. Wang: Online Aggregation. SIGMOD, 97.
  • Swarup Acharya, Phillip B. Gibbons, Viswanath Poosala, Sridhar Ramaswamy: Join Synopses for Approximate Query Answering. SIGMOD, 99.
  • Chris
  • Fei
  • 11/23
  • Brian Babcock, Surajit Chaudhuri: Towards a Robust Query Optimizer: A Principled and Practical Approach. SIGMOD Conference 2005: 119-130
  • Michelle
  • 11/30 Statistical Models II

  • Amol Deshpande, Minos N. Garofalakis, Rajeev Rastogi: Independence is Good: Dependency-Based Histogram Synopses for High-Dimensional Data. SIGMOD, 01.
  • Mike
  • 12/7 Wavelets

  • To be decided
  • ???

  • Seminar Description

    Our topic this quarter is Selectivity Estimation. While initially this area was motivated by a rather narrow class of applications, namely cost-based query optimizers, today it has much wider applications, from approximate query evaluation to probabilistic databases. We will select a combination of papers that include both some classic texts on histograms, and recent developments.
    Please sign up for the course mailing list here. Send mail to that list at cse590db at cs

    Previous CSE 590DBs:

    UW Database Group Web

    Last modified Fri Dec 5 12:47:09 PST 2003