Recent Directions in Approximate Nearest Neighbor Search

Abstract:
Nearest neighbor search is a fundamental data structure problem with numerous applications in machine learning, information retrieval, computer vision, recommendation systems, and beyond. Formally, given a collection P of n points in a d-dimensional space, the goal of the (Approximate) Nearest Neighbor problem is to construct a data structure that, given a query point q, quickly identifies a point from P that is (approximately) closest to q.

Despite extensive research on this topic, the basic formulation of nearest neighbor search faces challenges in addressing modern application needs. These challenges include reporting search results that satisfy constraints related to diversity, fairness, robustness, or differential privacy, as well as generalizing the problem to handle more complex objects or multiple queries. In this talk, I will survey our results for these variants of the problem.

Bio:
Sepideh Mahabadi is a senior researcher in MSR Redmond Algorithms group. Her research is mostly focused on theoretical foundations of massive data, including High Dimensional Computational Geometry, Streaming Algorithms, Data Summarization, as well as societal aspects of algorithms for massive data including diversity, fairness, and privacy. She earned her PhD in Computer Science, at the Theory of Computation group at MIT, where she was advised by Piotr Indyk. Following her PhD, she spent a year as a Postdoctoral Research Scientist at Columbia University, and three years as a Research Assistant Professor at the Toyota Technological Institute at Chicago (TTIC). She is a co-recipient of the ACM PODS Alberto O. Mendelzon Test-of-Time Award 2024.