Nearest-neighbor-preserving embeddings

Piotr Indyk; Assaf Naor

doi:10.1145/1273340.1273347

Nearest-neighbor-preserving embeddings

Piotr Indyk
, Assaf Naor

Research output: Contribution to journal › Article › peer-review

99 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 language	English (US)
Article number	1273347
Journal	ACM Transactions on Algorithms
Volume	3
Issue number	3
DOIs	https://doi.org/10.1145/1273340.1273347
State	Published - Aug 1 2007
Externally published	Yes

All Science Journal Classification (ASJC) codes

Mathematics (miscellaneous)

Keywords

Dimensionality reduction
Doubling spaces
Embeddings
Nearest neighbor

Access to Document

10.1145/1273340.1273347

Cite this

@article{75c4523abc2644499ea80dcdfaebb5f2,

title = "Nearest-neighbor-preserving embeddings",

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.",

keywords = "Dimensionality reduction, Doubling spaces, Embeddings, Nearest neighbor",

author = "Piotr Indyk and Assaf Naor",

year = "2007",

month = aug,

day = "1",

doi = "10.1145/1273340.1273347",

language = "English (US)",

volume = "3",

journal = "ACM Transactions on Algorithms",

issn = "1549-6325",

publisher = "Association for Computing Machinery (ACM)",

number = "3",

}

TY - JOUR

T1 - Nearest-neighbor-preserving embeddings

AU - Indyk, Piotr

AU - Naor, Assaf

PY - 2007/8/1

Y1 - 2007/8/1

N2 - 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.

AB - 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.

KW - Dimensionality reduction

KW - Doubling spaces

KW - Embeddings

KW - Nearest neighbor

UR - https://www.scopus.com/pages/publications/34548291868

UR - https://www.scopus.com/pages/publications/34548291868#tab=citedBy

U2 - 10.1145/1273340.1273347

DO - 10.1145/1273340.1273347

M3 - Article

AN - SCOPUS:34548291868

SN - 1549-6325

VL - 3

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

IS - 3

M1 - 1273347

ER -

Nearest-neighbor-preserving embeddings

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this