Sepideh Mahabadi: Approximate Nearest Line Search in High Dimensions

Thursday, December 11, 2014 - 4:00pm
Sepideh Mahabadi

We consider the Approximate Nearest Line Search (NLS) problem. Given a set L of N lines in the high dimensional Euclidean space R^d, the goal is to build a data structure that, given a query point q ∈ R^d, reports a line l ∈ L such that its distance to the query is within (1+ε) 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.


Our main result is a data structure that, for any fixed ε>0, reports the approximate nearest line in time (d + log N + 1/ε)^O(1) using O(N+d)^O(1/ε^2) space. This is the first high-dimensional data structure for this problem with poly-logarithmic query time and polynomial space. In contrast, the best previous data structure for this problem, due to Magen, required quasi-polynomial space. Up to polynomials, the bounds achieved by our data structure match the performance of the best algorithm for the approximate nearest neighbor problem for point sets.