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.
All Science Journal Classification (ASJC) codes
- Mathematics (miscellaneous)
- Dimensionality reduction
- Doubling spaces
- Nearest neighbor