Approximate nearest neighbor search for low-dimensional queries

Sariel Har-Peled, Nirman Kumar

Research output: Contribution to journalArticlepeer-review

Abstract

We study the approximate nearest neighbor problem for metric spaces where the query points are constrained to lie on a subspace of low doubling dimension, while the data is high dimensional. We show that this problem can be solved efficiently despite the high dimensionality of the data.

Original languageEnglish (US)
Pages (from-to)138-159
Number of pages22
JournalSIAM Journal on Computing
Volume42
Issue number1
DOIs
StatePublished - 2013

Keywords

  • Approximation algorithms
  • Computational geometry
  • Nearest neighbor
  • Voronoi diagram

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Approximate nearest neighbor search for low-dimensional queries'. Together they form a unique fingerprint.

Cite this