Approximate Line Nearest Neighbor in High Dimensions
Alexandr Andoni, Piotr Indyk, Robert Krauthgamer, Huy Lê Nguyễn · 2009
We consider the problem of approximate nearest neighbors in high dimensions, when the queries are lines. In this problem, given n points in R d, we want to construct a data structure to support efficiently the following queries: given a line L, report the point p closest to L. This problem generalizes the more familiar nearest neighbor problem. From a practical perspective, lines, and low-dimensional flats in general, may model data under linear variation, such as physical objects under different lighting. For approximation 1 + ɛ, we achieve a query time of d 3 n 0.5+t, for arbitrary small t> 0, with a space of d 2 n O(1/ɛ2 +1/t 2). To the best of our knowledge, this is the first algorithm for this problem with polynomial space and sub-linear query time. 1