Approximate nearest neighbor search for low-dimensional queries

Sariel Har-Peled, Nirman Kumar

Research output: Contribution to journalArticlepeer-review


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
Issue number1
StatePublished - 2013


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

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)


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

Cite this