Nearest-neighbor-preserving embeddings

Piotr Indyk, Assaf Naor

Research output: Contribution to journalArticlepeer-review

87 Scopus citations


In this article we introduce the notion of nearest-neighbor-preserving embeddings. These are randomized embeddings between two metric spaces which preserve the (approximate) nearest-neighbors. We give two examples of such embeddings for Euclidean metrics with low intrinsic dimension. Combining the embeddings with known data structures yields the best-known approximate nearest-neighbor data structures for such metrics.

Original languageEnglish (US)
Article number1273347
JournalACM Transactions on Algorithms
Issue number3
StatePublished - Aug 1 2007
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics (miscellaneous)


  • Dimensionality reduction
  • Doubling spaces
  • Embeddings
  • Nearest neighbor


Dive into the research topics of 'Nearest-neighbor-preserving embeddings'. Together they form a unique fingerprint.

Cite this