Learnability of Selectivity Functions
CS Distinguished Lecture Series
September 29, 2022
11:00 AM - 12:30 PM
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:
Date posted
Sep 15, 2022
Date updated
Sep 15, 2022