| MIT Abstract (2008) | |||||||||||||||
Abstract | |||||||||||||||
| In this paper 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. 1 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||