Your browser is unsupported

We recommend using the latest version of IE11, Edge, Chrome, Firefox or Safari.

Sep 29 2022

Learnability of Selectivity Functions

CS Distinguished Lecture Series

September 29, 2022

11:00 AM - 12:30 PM


ERF 1043


842 S. Morgan St., Chicago, IL 60607

Learnability of Selectivity Functions

Presenter: Pankaj K. Agarwal, Duke University

Abstract: Range searching is a widely studied problem both in computational geometry and database systems, and there have been recent advances in both fields. This talk discusses some of these recent advances and also explores the use of machine learning for estimating the selectivity of range queries in database systems. Using classic learning theory for real-valued functions based on shattering dimension, we show that the selectivity function of a range space with bounded VC-dimension is learnable. As many popular classes of queries (e.g., orthogonal range search, inequalities involving linear combination of attributes, distance-based search, etc.) represent range spaces with finite VC-dimension, our result immediately implies that their selectivity functions are also learnable. To the best of our knowledge, this is the first attempt at formally explaining the role of machine learning techniques in selectivity estimation, and complements the growing literature in empirical studies in this direction. 

Speaker bio: Pankaj K. Agarwal earned his PhD in computer science from the Courant Institute of Mathematical Sciences at New York University.  He joined Duke University in 1989, where he is now the RJR Nabisco Professor of Computer Science and Mathematics. He served as the chair of the department of computer science from 2004 to 2010, and again from 2017 to 2020. His research interests include geometric computing, geographic information systems, database systems, sensor networks, computational molecular biology, and robotics. A Sloan Fellow, an ACM Fellow, and a National Young Investigator, Agarwal has authored four books and more than 400 research articles. He is a co-founder of the start-up company Scalable Algorithmics, and he serves on the editorial boards of a number of journals and on the advisory boards of multiple institutes and centers.

Faculty host:


Abolfazl Asudeh

Date posted

Sep 15, 2022

Date updated

Sep 15, 2022