Approximate nearest neighbor queries revisited

Research output: Contribution to conferencePaperpeer-review

Abstract

This paper proposes new methods to answer approximate nearest neighbor queries on a set of n points in d-dimensional Euclidean space. For any fixed constant d, a data structure with O(ε(1-d)/2 n log n) preprocessing time and O(ε(1-d)/2 log n) query time achieves approximation factor 1+ε for any given 0<ε<1; a variant reduces the ε-dependence by a factor of ε-1/2. For any arbitrary d, a data structure with O(d2n log n) preprocessing time and O(d2 log n) query time achieves approximation factor O(d3/2).

Original languageEnglish (US)
Pages352-358
Number of pages7
DOIs
StatePublished - 1997
Externally publishedYes
EventProceedings of the 1997 13th Annual Symposium on Computational Geometry - Nice, Fr
Duration: Jun 4 1997Jun 6 1997

Other

OtherProceedings of the 1997 13th Annual Symposium on Computational Geometry
CityNice, Fr
Period6/4/976/6/97

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Approximate nearest neighbor queries revisited'. Together they form a unique fingerprint.

Cite this