We introduce a new variant of the nearest neighbor search problem, which allows for some coordinates of the dataset to be arbitrarily corrupted or unknown. Formally, given a dataset of @math points @math in high-dimensions, and a parameter @math , the goal is to preprocess the dataset, such that given a query point @math , one can compute quickly a point @math , such that the distance of the query to the point @math is minimized, when ignoring the "optimal" @math coordinates. Note, that the coordinates being ignored are a function of both the query point and the point returned. We present a general reduction from this problem to answering ANN queries, which is similar in spirit to LSH (locality sensitive hashing) [IM98]. Specifically, we give a sampling technique which achieves a bi-criterion approximation for this problem. If the distance to the nearest neighbor after ignoring @math coordinates is @math , the data-structure returns a point that is within a distance of @math after ignoring @math coordinates. We also present other applications and further extensions and refinements of the above result. The new data-structures are simple and (arguably) elegant, and should be practical -- specifically, all bounds are polynomial in all relevant parameters (including the dimension of the space, and the robustness parameter @math ).
Finally, several generalizations of the problem have been considered in the literature. Two related generalizations are the Nearest @math -flat Search and the Approximate Nearest @math -flat. In the former, the dataset is a set of @math -flats ( @math -dimensional affine subspace) instead of simple points but the query is still a point (see @cite_8 for example). In the latter however, the dataset consists of a set of points but the query is now a @math -flat (see for example @cite_15 @cite_14 ). We note that our problem cannot be solved using these variations (at least naively) since the set of coordinates that are being ignored in our problem are not specified in advance and varies for each query. This would mean that @math different subspaces are to be considered for each point. In our settings, both @math and @math can be quite large, and the new data-structures have polynomial dependency in both parameters.
@cite_15 @cite_14 @cite_8
1492925305 2398147718
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. For approximation 1 + e, we achieve a query time of d3n0.5+t, for arbitrary small t > 0, with a space of d2nO(1 e2+1 t2). To the best of our knowledge, this is the first algorithm for this problem with polynomial space and sub-linear query time. We consider the Approximate Nearest Line Search (NLS) problem. Given a set L of N lines in the high dimensional Euclidean space Rd, the goal is to build a data structure that, given a query point q ∈ Rd, reports a line l ∈ L such that its distance to the query is within (1 + e) 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 e > 0, reports the approximate nearest line in time (d + log N + 1 e)O(1) using O(N + d)O(1 e2) 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 [16], 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.