Nearest-neighbor-preserving embeddings

Piotr Indyk, Assaf Naor

Research output: Contribution to journalArticle

69 Scopus citations

Abstract

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
Volume3
Issue number3
DOIs
StatePublished - Aug 1 2007
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics (miscellaneous)

Keywords

  • Dimensionality reduction
  • Doubling spaces
  • Embeddings
  • Nearest neighbor

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

  • Cite this