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 | |
State | Published - Aug 1 2007 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Mathematics (miscellaneous)
Keywords
- Dimensionality reduction
- Doubling spaces
- Embeddings
- Nearest neighbor