Approximate line nearest neighbor in high dimensions

摘要

We consider the problem of approximate nearest neighbors in high dimensions, when the queries are lines. In this problem, given n points in Rd, 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.