License:
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2017.4
URN: urn:nbn:de:0030-drops-78182
URL: https://drops.dagstuhl.de/opus/volltexte/2017/7818/
Agarwal, Pankaj K. ;
Rubin, Natan ;
Sharir, Micha
Approximate Nearest Neighbor Search Amid Higher-Dimensional Flats
Abstract
We consider the Approximate Nearest Neighbor (ANN) problem where the input set consists of n k-flats in the Euclidean Rd, for any fixed parameters k<d, and where, for each query point q, we want to return an input flat whose distance from q is at most (1 + epsilon) times the shortest such distance, where epsilon > 0 is another prespecified parameter. We present an algorithm that achieves this task with n^{k+1}(log(n)/epsilon)^O(1) storage and preprocessing (where the constant of proportionality in the big-O notation depends on d), and can answer a query in O(polylog(n)) time (where the power of the logarithm depends on d and k). In particular, we need only near-quadratic storage to answer ANN queries amidst a set of n lines in any fixed-dimensional Euclidean space. As a by-product, our approach also yields an algorithm, with similar performance bounds, for answering exact nearest neighbor queries amidst k-flats with respect to any polyhedral distance function. Our results are more general, in that they also
provide a tradeoff between storage and query time.
BibTeX - Entry
@InProceedings{agarwal_et_al:LIPIcs:2017:7818,
author = {Pankaj K. Agarwal and Natan Rubin and Micha Sharir},
title = {{Approximate Nearest Neighbor Search Amid Higher-Dimensional Flats}},
booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)},
pages = {4:1--4:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-049-1},
ISSN = {1868-8969},
year = {2017},
volume = {87},
editor = {Kirk Pruhs and Christian Sohler},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7818},
URN = {urn:nbn:de:0030-drops-78182},
doi = {10.4230/LIPIcs.ESA.2017.4},
annote = {Keywords: Approximate nearest neighbor search, k-flats, Polyhedral distance functions, Linear programming queries}
}
Keywords: |
|
Approximate nearest neighbor search, k-flats, Polyhedral distance functions, Linear programming queries |
Collection: |
|
25th Annual European Symposium on Algorithms (ESA 2017) |
Issue Date: |
|
2017 |
Date of publication: |
|
01.09.2017 |