Author Archive

EDBT 2012 Accepted Paper

February 11th, 2012
Comments Off

The Brown Data Management Research Group has the following paper in EDBT 2012:

  • Optimizing Index Deployment Order for Evolving OLAP
      Hideaki Kimura, Carleton Coffrin, Alexander Rasin, Stanley Zdonik

    Many database applications need hundreds or thousands of indexes to speed up query execution, making performance tuning a difficult task for database administrators. The well-known problem of index selection is to automatically design an optimal set of indexes on behalf of DBAs. This paper brings a new perspective to the problem with a scalable and extensible solution. We study the problem of optimizing the order of index creation to achieve prompt query runtime improvements and also reduce the index deployment time. We found that traditional approaches, such as A* search and MIP, are not suitable for this problem. Instead, we demonstrate that Constraint Programming is an efficient and flexible solution for this problem and its future extension. Our experimental results show that our pruning techniques can reduce the size of the search space by many orders of magnitude, and we verify that our local search algorithm based on CP is a highly scalable and stable method for quickly finding the best known solutions.

Accepted Papers

Graduation: Mert Akdere

September 7th, 2011
Comments Off

Mert Akdere has completed his Ph.D. and joined Google. Congratulations!
His Doctoral Thesis is available here


ECML PKDD 2011 Accepted Paper

June 14th, 2011
Comments Off

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.

Accepted Papers