报告题目：Sampling-based Methods for Inner Product Sketching

报告时间：2024年8月26日14:30-15:30

报告地点：计算机学院B404

报告人：Christopher Musco

报告人国籍：美国

报告人单位：New York University

报告人简介：Christopher Musco is an assistant professor of Computer Science and Engineering at New York University. He is a member of NYU's Theoretical Computer Science group and the Visualization, Data Analysis, and Imaging Center (VIDA Center). His research focuses on the design and theoretical analysis of randomized algorithms with applications in computational mathematics, machine learning, and databases. Professor Musco's work has been funded by the US Department of Energy and National Science Foundation, including through an NSF CAREER Award.

报告摘要：I will discuss new "sketching'' methods that can accurately estimate the inner product between any two vectors based on a small compression (or "sketch") of those vectors. Sketches for estimating inner products find applications across databases (for join-size estimation, correlation estimation, and more) and machine learning (for model evaluation, similarity computation, and vector search). Prior state-of-the-art sketching methods for inner products are based on Johnson-Lindenstrauss (JL) random projection and related methods. In contrast, the methods I will discuss are based on an old and powerful technique called "coordinated random sampling". I will prove that our sampling-based sketches enjoy stronger worst-case theoretical guarantees than sketches based on JL projection, and also perform better in practice across a wide variety of applications.

邀请人：王胜