RISE Seminar 1/18/18: Nearest Neighbor Search: Theory and Practice, by Ludwig Schmidt

January 18, 2018

Title: Nearest Neighbor Search: Theory and Practice

By: Ludwig Schmidt

Affiliation: Postdoc, UC Berkeley EECS

Where/When: Thursday Jan 18 noon-1pm Wozniak Lounge (430 Soda Hall)

Abstract: Nearest neighbor search is a fundamental algorithmic primitive when dealing with large datasets: given a new query, the goal is to find the closest point in the dataset. For real-time applications, it is especially important to process nearest neighbor queries with low latency, even for high-dimensional data such as images and videos. In this talk, I will give an overview of the theory and practice of nearest neighbor search, both of which have seen significant progress over the past few years. The focus will be on the Locality-Sensitive Hashing (LSH) framework and how it compares to other algorithms. Recent work on LSH shows that a specific hash family (the cross-polytope hash) combines strong theoretical guarantees with good empirical performance. Moreover, the structure of LSH algorithms makes them suitable for highly parallel and distributed implementations.

Based on joint works with Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya Razenshteyn, and Kunal Talwar.

Bio: Ludwig Schmidt is a PhD student at MIT (advised by Piotr Indyk) and will be a postdoc at UC Berkeley starting in March 2018. Ludwig’s research interests revolve around algorithmic aspects of machine learning and statistics. Ludwig received a Google PhD Fellowship, a Simons-Berkeley research fellowship, and a best paper award at the International Conference on Machine Learning (ICML).