Sepideh Mahabadi

PhD. Candidate

Approximate Nearest Neighbor and Its Many Variants

  Computer Engineering Department, Floor 4, Kharazmi Hall
  Thursday, 31 December 2015
  09:00 - 10:00

Abstract

In the first half of the talk, I will go over a short introduction to the Approximate Nearest Neighbor problem, followed by several variations of the problem and their applications. In the second half, I will talk in more details about one of the variations, namely the Approximate Nearest Line Search.

In the Approximate Nearest Line Search (NLS) problem, we are given a set L of N lines in the high dimensional Euclidean space, and the goal is to build a data structure that, given a query point q, reports an approximate closest line in L to the query. That is, a line in L such that its distance to the query is within (1+eps) factor of the distance of the closest line to the query point q. The problem is a natural generalization of the well-studied Approximate Nearest Neighbor problem for point sets (ANN), and is a natural first step towards understanding how to build efficient nearest-neighbor data structures for objects that are more complex than points.

Bio

Sepideh Mahabadi is a PhD student at the Theory of Computing group at the Computer Science department of MIT. She received her B.Sc. in 2011 from the Computer Engineering Department of Sharif University and her Master's degree from MIT in 2013. Her research is mostly focused on High Dimensional Computational Geometry and Streaming Algorithms.