ECML PKDD 2011 Accepted Paper
The Brown Data Management Group has the following paper in ECML PKDD:
- The VC-Dimension of SQL Queries and Selectivity Estimation Through SamplingMatteo Riondato, Mert Akdere, Ugur Cetintemel, Stan Zdonik, Eli Upfal (Project Longview)
This paper studies a new method to evaluate the selectivity of SQL queries which exploits VC-dimension. We devised an explicit bound on the VC-dimension of a range space defined by all possible outcomes of queries. VC-dimension is a function of maximum complexity of queries, not of the number of queries nor of the size of the database. By exploiting it, with high probability, we can accurately estimate the selectivity of any queries from a concise random sample.
The European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD) will take place in Athens, Greece from September 5th to 9th, 2011.
Editorial Note: From this issue, we have started giving a brief introduction of each paper announced on our website, inspired by the University of Washington Database group website.
We are glad to hear any questions or comments you may have. Feel free to contact the authors if you are interested. Camera ready versions of the papers are usually available after the camera-ready submission due date.