Approximate line nearest neighbor in high dimensions
Lists
Only you see this
Abstract
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 + ε, we achieve a query time of d3n0.5+t, for arbitrary small t > 0, with a space of d2nO(1/ε2+1/t2). To the best of our knowledge, this is the first algorithm for this problem with polynomial space and sub-linear query time.
BibTeX
@inproceedings{andoni2009approximate,
author = {Alexandr Andoni and Piotr Indyk and Robert Krauthgamer and Huy L. Nguyen},
title = {{Approximate line nearest neighbor in high dimensions}},
booktitle = {SODA},
year = {2009},
doi = {10.1137/1.9781611973068.33},
}Loading related content...