Math @ Duke

Publications [#329363] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Rubin, N; Sharir, M, Approximate nearest neighbor search amid higherdimensional flats,
Leibniz International Proceedings in Informatics, Lipics, vol. 87
(September, 2017), ISBN 9783959770491 [doi]
(last updated on 2019/01/21)
Abstract: © Pankaj K. Agarwal, Natan Rubin, and Micha Sharir. We consider the approximate nearest neighbor (ANN) problem where the input set consists of n kflats in the Euclidean Rd, for any fixed parameters 0 ≤ k < d, and where, for each query point q, we want to return an input flat whose distance from q is at most (1 + ϵ) times the shortest such distance, where ϵ > 0 is another prespecified parameter. We present an algorithm that achieves this task with nk+1(log(n)/ ϵ)O(1) storage and preprocessing (where the constant of proportionality in the bigO 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 nearquadratic storage to answer ANN queries amid a set of n lines in any fixeddimensional Euclidean space. As a byproduct, our approach also yields an algorithm, with similar performance bounds, for answering exact nearest neighbor queries amid kflats with respect to any polyhedral distance function. Our results are more general, in that they also provide a tradeoff between storage and query time.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

