Nearest-neighbor-preserving embeddings

Piotr Indyk; Assaf Naor

doi:10.1145/1273340.1273347

Nearest-neighbor-preserving embeddings

Piotr Indyk, Assaf Naor

Mathematics

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

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

Keywords

Dimensionality reduction
Doubling spaces
Embeddings
Nearest neighbor

ASJC Scopus subject areas

Mathematics (miscellaneous)

Access to Document

10.1145/1273340.1273347

Cite this

@article{e5c7a6a613c5454ea00344421db5a3d2,

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 - http://www.scopus.com/inward/record.url?scp=34548291868&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34548291868&partnerID=8YFLogxK

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

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this